Showing posts with label Coding Day 30. Show all posts
Showing posts with label Coding Day 30. Show all posts

Tuesday, March 1, 2022

Predecessor and Successor of an Element

I/P:

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

110

O/P:

Predecessor = 80

Successor = 120


package pep.Day30;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Predecessor_and_Successor_of_Element {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    static Node predecessor, successor;
    static int state;

    private static void predecessorAndSuccessor(Node node, int data) {
        if (state == 0) {
            if (node.data == data)
                state = 1;
            else
                predecessor = node;
        } else if (state == 1) {
            successor = node;
            state = 2;
        }
        for (Node child : node.children) {
            predecessorAndSuccessor(child, data);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }
        int data = Integer.parseInt(br.readLine());
        Node root = construct(arr);
        predecessor = null;
        successor = null;
        state = 0;
        predecessorAndSuccessor(root, data);

        if (predecessor == null)
            System.out.println("Predecessor = Not found");
        else
            System.out.println("Predecessor = " + predecessor.data);


        if (successor == null)
            System.out.println("Successor = Not found");
        else
            System.out.println("Successor = " + successor.data);

    }


}


Time Complexity: O(n)

The time complexity of the above solution is O(n) as we are traversing all the nodes of the tree.

Space Complexity: O(1)

The space complexity of the above solution is O(1) as we have not used any extra memory. But, if we consider the recursion space then it is O(logn) as the max height of the recursion stack will be equal to height of the tree i.e. O(logn).




at No comments:
Labels: ,

Generic Tree - Multisolver - TRAVEL and CHANGE : size, height, min, max

I/P:
24
10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:
size = 12
min = 10
max = 120
height = 3


we are updating values in pre-order traversal only.


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class MultiSolver {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    static int size, min, max, height;

    private static void multiSolver(Node node, int depth) {
        size++;
        min = Math.min(min, node.data);
        max = Math.max(max, node.data);
        height = Math.max(height, depth);

        for (Node child : node.children)
            multiSolver(child, depth + 1);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        size = 0;
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        height = 0;
        multiSolver(root, 0);
        System.out.println("size = " + size);
        System.out.println("min = " + min);
        System.out.println("max = " + max);
        System.out.println("height = " + height);
        // display(root);
    }


}



at No comments:
Labels: ,

Is Generic Tree Symmetric

I/O:
20
10 20 50 -1 60 -1 -1 30 70 -1 80 -1 90 -1 -1 40 100 -1 110 -1 -1 -1

O/P: true


    



import java.io.*;
import java.util.*;

public class Main {
  private static class Node {
    int data;
    ArrayList<Node> children = new ArrayList<>();
  }

  public static void display(Node node) {
    String str = node.data + " -> ";
    for (Node child : node.children) {
      str += child.data + ", ";
    }
    str += ".";
    System.out.println(str);

    for (Node child : node.children) {
      display(child);
    }
  }

  public static Node construct(int[] arr) {
    Node root = null;

    Stack<Node> st = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == -1) {
        st.pop();
      } else {
        Node t = new Node();
        t.data = arr[i];

        if (st.size() > 0) {
          st.peek().children.add(t);
        } else {
          root = t;
        }

        st.push(t);
      }
    }

    return root;
  }

  public static int size(Node node) {
    int s = 0;

    for (Node child : node.children) {
      s += size(child);
    }
    s += 1;

    return s;
  }

  public static int max(Node node) {
    int m = Integer.MIN_VALUE;

    for (Node child : node.children) {
      int cm = max(child);
      m = Math.max(m, cm);
    }
    m = Math.max(m, node.data);

    return m;
  }

  public static int height(Node node) {
    int h = -1;

    for (Node child : node.children) {
      int ch = height(child);
      h = Math.max(h, ch);
    }
    h += 1;

    return h;
  }

  public static boolean IsSymmetric(Node node) {
    // write your code here
  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    String[] values = br.readLine().split(" ");
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(values[i]);
    }

    Node root = construct(arr);
    boolean sym = IsSymmetric(root);
    System.out.println(sym);
    // display(root);
  }

}




at No comments:
Labels: ,

Are Trees Mirror In Shape

I/P:

12 10 20 -1 30 50 -1 60 -1 -1 40 -1 -1 12 100 200 -1 300 500 -1 600 -1 -1 400 -1 -1


O/P: true

1. Compare the size of parent node

2. Compare the size of children of Node_1's first child and Node_2's last child

package pep.Day30;

import java.io.*;
import java.util.*;

public class Are_Trees_Mirror_In_Shape {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static boolean areMirror(Node n1, Node n2) {
        if (n1.children.size() != n2.children.size())
            return false;

        for (int i = 0; i < n1.children.size(); i++) {
            Node c1 = n1.children.get(i);
            Node c2 = n2.children.get(n2.children.size() - 1 - i);
            boolean bool = areMirror(c1, c2);
            if (!bool)
                return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n1 = Integer.parseInt(br.readLine());
        int[] arr1 = new int[n1];
        String[] values1 = br.readLine().split(" ");
        for (int i = 0; i < n1; i++) {
            arr1[i] = Integer.parseInt(values1[i]);
        }
        Node root1 = construct(arr1);

        int n2 = Integer.parseInt(br.readLine());
        int[] arr2 = new int[n2];
        String[] values2 = br.readLine().split(" ");
        for (int i = 0; i < n2; i++) {
            arr2[i] = Integer.parseInt(values2[i]);
        }
        Node root2 = construct(arr2);

        boolean mirror = areMirror(root1, root2);
        System.out.println(mirror);
    }

}




at No comments:
Labels: ,

Are Trees Similar In Shape

I/P: 

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1 24 1 2 5 -1 6 -1 -1 3 7 -1 8 11 -1 12 -1 -1 9 -1 -1 4 10 -1 -1 -1


O/P: true


1. first verify the size of children of both the nodes

2. if same, then tell their children to check their children further.



package pep.Day30;

import java.io.*;
import java.util.*;

public class Are_Trees_Similar_In_Shape {

    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static boolean areSimilar(Node n1, Node n2) {
        // write your code here
        if (n1.children.size() != n2.children.size())
            return false;
        else {
            for (int i = 0; i < n1.children.size(); i++) {
                boolean bool = areSimilar(n1.children.get(i), n2.children.get(i));
                if (!bool)
                    return false;
            }
        }

        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n1 = Integer.parseInt(br.readLine());
        int[] arr1 = new int[n1];
        String[] values1 = br.readLine().split(" ");
        for (int i = 0; i < n1; i++) {
            arr1[i] = Integer.parseInt(values1[i]);
        }
        Node root1 = construct(arr1);

        int n2 = Integer.parseInt(br.readLine());
        int[] arr2 = new int[n2];
        String[] values2 = br.readLine().split(" ");
        for (int i = 0; i < n2; i++) {
            arr2[i] = Integer.parseInt(values2[i]);
        }
        Node root2 = construct(arr2);

        boolean similar = areSimilar(root1, root2);
        System.out.println(similar);
    }

}



at No comments:
Labels: ,
Subscribe to: Posts (Atom)

Diagonal Traversal

 eg.  1       2       3       4 5      6       7       8 9    10    11     12 13  14   15    16 Output: 1 6 11 16 2 7 12 3 8 4  Approach:...

  • LeetCode 7. Reverse Integer
    https://leetcode.com/problems/reverse-integer/description/ Integer.MAX_VALUE = 2,147,483,647 =  2 31 - 1 Integer.MIN_VALUE = -2,147,483,64...
  • Leet Code 1: Two Sum
    https://leetcode.com/problems/two-sum/description/    Given the constraints: 2 <= nums.length <= 10⁴ -10⁹ <= nums[i] <= 10⁹ -10...
  • LeetCode 2027. Minimum Moves to Convert String
    https://leetcode.com/problems/minimum-moves-to-convert-string/   Example 1: Input: s = "XXX" Output: 1 Explanation: XXX -> ...