Skip to content

Instantly share code, notes, and snippets.

@neversettlejay
Forked from krishnadey30/LeetCodeQuestions.md
Last active May 27, 2024 13:49
Show Gist options
  • Save neversettlejay/83ee7338580236fa9ff4ede0322b90cb to your computer and use it in GitHub Desktop.
Save neversettlejay/83ee7338580236fa9ff4ede0322b90cb to your computer and use it in GitHub Desktop.
Ω(Blind 75 + Grind 75 + N)

Array


Binary


Dynamic Programming


Graph


Interval


Linked List


Matrix


String


Tree


Heap


Backtracking


Important Links:

  1. 14 Patterns to Ace Any Coding Interview Question

  2. Leet code solution

  3. Trie implementation


Not a part of Blind 75

Graph

Dynamic Programming


Solutions:

1) Merge K sorted Lists:

/*package whatever //do not write package name here */

import java.io.*;


     class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    
public class GFG {


    private ListNode mergeLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;

        ListNode dummyNode = new ListNode(-1);
        ListNode resultIterator = dummyNode;

        ListNode l1Iterator = l1;
        ListNode l2Iterator = l2;

        while (l1Iterator != null && l2Iterator != null) {
            if (l1Iterator.val < l2Iterator.val) {
                resultIterator.next = l1Iterator;
                resultIterator = resultIterator.next;
                l1Iterator = l1Iterator.next;
            } else {
                resultIterator.next = l2Iterator;
                resultIterator = resultIterator.next;
                l2Iterator = l2Iterator.next;
            }
        }

        if (l1Iterator != null)
            resultIterator.next = l1Iterator;

        if (l2Iterator != null)
            resultIterator.next = l2Iterator;

        return dummyNode.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;

        return mergeKListsUtility(lists, 0, lists.length - 1);
    }

    private ListNode mergeKListsUtility(ListNode[] lists, int low, int high) {
        if (low > high)
            return null;
        else if (low == high)
            return lists[low];
        else {
            int mid = low + (high - low) / 2;
            ListNode left = mergeKListsUtility(lists, low, mid);
            ListNode right = mergeKListsUtility(lists, mid + 1, high);
            return mergeLists(left, right);
        }
    }

public static void main(String[] args) {
    // Create test linked lists
    ListNode list1 = new ListNode(1);
    list1.next = new ListNode(4);
    list1.next.next = new ListNode(5);

    ListNode list2 = new ListNode(1);
    list2.next = new ListNode(3);
    list2.next.next = new ListNode(4);

    ListNode list3 = new ListNode(2);
    list3.next = new ListNode(6);

    // Create an instance of GFG class
    GFG gfg = new GFG();

    // Create an array of linked lists
    ListNode[] lists = {list1, list2, list3};

    // Merge the lists
    ListNode mergedList = gfg.mergeKLists(lists);

    // Print the merged list
    while (mergedList != null) {
        System.out.print(mergedList.val + " ");
        mergedList = mergedList.next;
    }
}

}


2) Jump Game I

class Solution {
    public boolean canJump(int[] nums) {
        
        int definiteDestination=nums.length-1;

        for (int stepsInTheNewDestination=nums.length-2;
        stepsInTheNewDestination>=0;
        stepsInTheNewDestination--){

            if(
                nums[stepsInTheNewDestination]
                +
                stepsInTheNewDestination
                >=
                definiteDestination
                ) 
                definiteDestination=stepsInTheNewDestination;
        }
        
        return definiteDestination==0;

    }
}

3) Jump Game II


class Solution {
    public int jump(int[] nums) {
        return jumpGameTwo(nums);
    }


        
      public static int jumpGameTwo(int[] jumpLogs) {
        Integer[] logs = new Integer[jumpLogs.length]; // minimum jumps log array
        // As the first is the initial position and last index is the destination.
        logs[jumpLogs.length - 1] = 0;

        // traverse from behind
        for (int individualTile = jumpLogs.length - 2; individualTile >= 0; individualTile--) {
            int stepsAvailableToJumpFromThisTile = jumpLogs[individualTile];

            // traverse from that index to the steps it can go because of it's capacity
            // And find that tiles in the reach of the present tile that has some value in logs array and not null, and if there are multiple values in the tiles that are reachable from the present tile then consider that
            int minimumJumpsToReactDestinationFromPresentTile = Integer.MAX_VALUE;

            for (int potentialReach = 1; potentialReach <= stepsAvailableToJumpFromThisTile && individualTile + potentialReach < jumpLogs.length; potentialReach++) {
                if (logs[individualTile + potentialReach] != null && logs[individualTile + potentialReach] < minimumJumpsToReactDestinationFromPresentTile) {
                    minimumJumpsToReactDestinationFromPresentTile = logs[individualTile + potentialReach];
                }
            }
            if (minimumJumpsToReactDestinationFromPresentTile != Integer.MAX_VALUE) {
                logs[individualTile] = minimumJumpsToReactDestinationFromPresentTile + 1;
            }
        }

  
        return logs[0];
    }
    
}

4) Find Median from Data Stream

class MedianFinder {

    private PriorityQueue<Integer> maxHeap = null;
    private PriorityQueue<Integer> minHeap=null;

    public MedianFinder() {
        maxHeap=new PriorityQueue<Integer>((a,b)-> b-a);
        minHeap=new PriorityQueue<Integer>((a,b)-> a-b);
    }   
    
    public void addNum(int num) {
        // start inserting element from the max heap 
        // check if the topmost element is greater than num in max heap then add num to the maxheap 
        // else add it to the min heap
        // call the balance method to balance the number of nodes in each heap

        if(maxHeap.size()==0||maxHeap.peek()>=num) maxHeap.offer(num);
        else minHeap.offer(num);


//  as min heap and max heap are global variables we dont need to pass the value
        balanceMinHeapAndMaxHeapSizes();
    }

         private void balanceMinHeapAndMaxHeapSizes(){

                if(maxHeap.size()-minHeap.size()>1)    minHeap.offer(maxHeap.poll());
                

                if(minHeap.size()-maxHeap.size()>1) maxHeap.offer(minHeap.poll());


            }
    
    public double findMedian() {

        if(maxHeap.size()==minHeap.size())   return  (maxHeap.peek()+minHeap.peek())/2.0;
        if(maxHeap.size()>minHeap.size()) return maxHeap.peek();
        if(maxHeap.size()<minHeap.size()) return minHeap.peek();
        return 0.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

5) House Rober 1


class Solution {
    public int rob(int[] nums) {


        // imagine if there are no house to rob
        if(nums.length==0) return 0;
        // imagine if we want to rob only 1 house
        if(nums.length==1) return nums[0];
        // imagine if there are only to robbable houses

        if(nums.length==2) return Math.max(nums[0],nums[1]);
        // imagine if there are more than 2 robbable house
        
        int[] maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice=new int[nums.length];
        maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[0]=nums[0];
        maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[1]=Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length;i++){

            maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i]/*Initializing valid rob entry with the sum of valid previous robs */=Math.max(
            (maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-2]+nums[i])/*Safe rob possibility 1 */
            ,
            (maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-1])/*Safe rob possibility 2 */
            );
        }

    return maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[nums.length-1];

    }
}

6) House Robbers II


class Solution {
    public int rob(int[] nums) {
        

        // imagine if there are no house to rob
        if(nums.length==0) return 0;
        // imagine if we want to rob only 1 house
        if(nums.length==1) return nums[0];
        // imagine if there are only to robbable houses

        if(nums.length==2) return Math.max(nums[0],nums[1]);
        // imagine if there are more than 2 robbable house
        
        int[] numsWithoutFirst = new int[nums.length - 1];
        int[] numsWithoutLast = new int[nums.length - 1];
        
        // Copy nums array without the first element
        System.arraycopy(nums, 1, numsWithoutFirst, 0, nums.length - 1);
        // Copy nums array without the last element
        System.arraycopy(nums, 0, numsWithoutLast, 0, nums.length - 1);

        return Math.max(houseRoberOne(numsWithoutFirst), houseRoberOne(numsWithoutLast));
    }
    
       public int houseRoberOne(int[] nums) {


        // imagine if there are no house to rob
        if(nums.length==0) return 0;
        // imagine if we want to rob only 1 house
        if(nums.length==1) return nums[0];
        // imagine if there are only to robbable houses

        if(nums.length==2) return Math.max(nums[0],nums[1]);
        // imagine if there are more than 2 robbable house
        
        int[] maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice=new int[nums.length];
        maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[0]=nums[0];
        maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[1]=Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length;i++){

            maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i]/*Initializing valid rob entry with the sum of valid previous robs */=Math.max(
            (maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-2]+nums[i])/*Safe rob possibility 1 */
            ,
            (maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[i-1])/*Safe rob possibility 2 */
            );
        }

    return maxAmountOfMoneyWeCouldStoreWithoutAlertingPolice[nums.length-1];

    }
}


7) Top K frequent elements

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Create a map to store the frequency of each number
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Create a priority queue to store ElementLog objects
        PriorityQueue<ElementLog> pq = new PriorityQueue<>(new ElementLogsComparator());

        // Iterate over the frequency map and add elements to the priority queue
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int element = entry.getKey();
            int frequency = entry.getValue();
            pq.offer(new ElementLog(element, frequency));
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // Create a result array and populate it with the top k frequent elements
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.poll().getElement();
        }

        return result;
    }
}

class ElementLogsComparator implements Comparator<ElementLog> {
    @Override
    public int compare(ElementLog element1, ElementLog element2) {
        return Integer.compare(element1.getFrequency(), element2.getFrequency());
    }
}

class ElementLog {
    private int element;
    private int frequency;

    public ElementLog(int element, int frequency) {
        this.element = element;
        this.frequency = frequency;
    }

    public int getElement() {
        return element;
    }

    public int getFrequency() {
        return frequency;
    }
}

8) Sum two integers

class Solution {
    public int getSum(int a, int b) {


        // 1 0 0 1 | a = 9
        // 1 0 1 1 | b = 11
        // 0 0 1 0 | XOR
        // 1 0 0 1 | AND
        // 1 0 0 1 0 | a&b << 1

        //now add (a&b << 1) and XOR a,b

        //now to add them again using xor and left shift we need to repeat that again till there is no carray left
      while(b !=0 ) {
          int temporaryCarry=(a&b)<<1;
        a = a ^ b;// xor does add the number but doesnt take care of the carry

        b = temporaryCarry;
      }
      // we are storing the result in a and carry in b
      return a;
        
    }
}

9) Number of 1 Bits

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int countNumberOfOnes=0;
        while(n!=0){
           // if last digit is 1  count one and right shift until entire number becomes 0.   
/*            countNumberOfOnes+=n%2;
            n=n>>1;
            */

            // secondly we can subtract 1 from the original number so we are basically subtracting a bit
            n&=(n-1);
          countNumberOfOnes++;
        }
        return countNumberOfOnes;
    }
}


10) Counting bits


class Solution {
    public int[] countBits(int n) {
        int[] dp=new int[n+1];
        int offset=1;
        for(int i=1;i<=n;i++){ 

            if((offset*2)==i)    offset=i;
            dp[i]=1+dp[i-offset];
            
        }
        return dp;
    }
}

10) Minimum window sub-string


class Solution
{
  public String minWindow (String s, String t)
  {
    return minimumWindowSubstring (s, t);
  }


  public static String minimumWindowSubstring (String completeString,
					       String subString)
  {
    String result = "";
    HashMap < Character, Integer > frequencySubStringMap = new HashMap <> ();

    for (int i = 0; i < subString.length (); i++)
      {
	char character = subString.charAt (i);
	frequencySubStringMap.put (character,
				   frequencySubStringMap.
				   getOrDefault (character, 0) + 1);
      }

    int matchCount = 0;		// number of counts of characters being considered in substring
    int desiredMatchCount = subString.length ();

    HashMap < Character, Integer > frequencyCompleteStringMap =
      new HashMap <> ();
    int i = -1;
    int j = -1;

    while (true)
      {
	boolean flag1 = false;
	boolean flag2 = false;

	// Acquire elements
	while (i < completeString.length () - 1
	       && matchCount < desiredMatchCount)
	  {
	    i++;		// Until the matchCount is less than the desired matchCount
	    char ch = completeString.charAt (i);
	    frequencyCompleteStringMap.put (ch,
					    frequencyCompleteStringMap.
					    getOrDefault (ch, 0) + 1);

	    if (frequencyCompleteStringMap.getOrDefault (ch, 0) <=
		frequencySubStringMap.getOrDefault (ch, 0))
	      {
		matchCount++;
	      }

	    flag1 = true;
	  }

	// Collect answers and release
	while (j < i && matchCount == desiredMatchCount)
	  {
	    String potentialResult = completeString.substring (j + 1, i + 1);

	    if (result.length () == 0
		|| potentialResult.length () < result.length ())
	      {
		result = potentialResult;
	      }

	    j++;
	    char ch = completeString.charAt (j);

	    if (frequencyCompleteStringMap.get (ch) == 1)
	      {
		frequencyCompleteStringMap.remove (ch);
	      }
	    else
	      {
		frequencyCompleteStringMap.put (ch,
						frequencyCompleteStringMap.
						get (ch) - 1);
	      }

	    if (frequencyCompleteStringMap.getOrDefault (ch, 0) <
		frequencySubStringMap.getOrDefault (ch, 0))
	      {
		matchCount--;
	      }

	    flag2 = true;
	  }

	if (!flag1 && !flag2)
	  {
	    break;
	  }
      }

    return result;
  }



}


11) Reverse bits

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        
        int result=0;

        for(int i=0;i<32;i++){

            result<<=1;//left shift result 

            if((n&1)==1)// to check whether last bit is one or 0
            //if one
            result++; // add that last bit of n to result and int the next iteration it will be right shifted and will be gone to right place to reveres bits

            //now right shift the number
            n>>=1;

        }


return result;
    }
}

12) Missing number


class Solution {
    public int missingNumber(int[] nums) {
        //the principle here is if we xor number with 0 we get number itself 
        //and if we xor number with itself we get 0
            int result = nums.length;
            int xor1=0;
            int xor2=0;

        for (int i = 0; i <=nums.length; i++) {
            xor1^=i;
        } // as we are given all the numbers will fall in the range of 0 to nums.length 


        for (int i = 0; i < nums.length; i++) {
            xor2^=nums[i];
        }
        //all the numbers that exist will cancel each other and only the one left will be the missing one

        return xor1^xor2;


    }
}


13) Decode ways


class Solution {
    public int numDecodings(String s) {
        if (s.length() == 1) {
            if (s.charAt(0) == '0')
                return 0;
        }

        int[] dp = new int[s.length()];
        dp[0] = 1;

        if (s.length() >= 2) {
            if (s.charAt(0) == '0')
                return 0;
        }

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i - 1) == '0' && s.charAt(i) == '0') {
                dp[i] = 0;
            } else if (s.charAt(i - 1) == '0' && s.charAt(i) != '0') {
                dp[i] = dp[i - 1];
            } else if (s.charAt(i - 1) != '0' && s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2')
                    dp[i] = (i >= 2 ? dp[i - 2] : 1);
                else
                    dp[i] = 0;
            } else if (s.charAt(i - 1) != '0' && s.charAt(i) != '0') {
                if (Integer.parseInt(s.substring(i - 1, i + 1)) <= 26)
                    dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 1);
                else
                    dp[i] = dp[i - 1];
            }
        }
        return dp[s.length() - 1];
    }
}


14) Alien Dictionary


class Solution
{
    public String findOrder(String [] dict, int N, int K)
    {
        // Write your code here
        return alienOrder(dict);
        
        
    }
    
        public String alienOrder(String[] words) {

        HashMap<Character, HashSet<Character>> map = new HashMap<>();
        HashMap<Character, Integer> indegree = new HashMap<>();

        for (String st : words) {

            for (char ch : st.toCharArray()) {
                indegree.put(ch, 0);
            }

        }

        for (int i = 0; i < words.length - 1; i++) {
            String curr = words[i];
            String next = words[i + 1];
            boolean mismatchFlag = false;
            int len = Math.min(curr.length(), next.length());
            for (int j = 0; j < len; j++) {
                char ch1 = curr.charAt(j);
                char ch2 = next.charAt(j);
                if (ch1 != ch2) {// then we can derive conclusion regarding which character will be before which
                                 // character

                    HashSet<Character> set = new HashSet<>();
                    if (map.containsKey(ch1) == true) {
                        set = map.get(ch1);
                        if (set.contains(ch2) == false) {
                            set.add(ch2);
                            indegree.put(ch2, indegree.get(ch2) + 1);
                            map.put(ch1, set);
                        }

                    } else {
                        // if adjacency list doesnt contain ch2
                        set.add(ch2);
                        indegree.put(ch2, indegree.get(ch2) + 1);
                        map.put(ch1, set);
                    }
                    mismatchFlag = true;
                    break;
                }
            }
            if (mismatchFlag == false && curr.length() > next.length()) {
                return "";

            }
        }
        // topological sort
        LinkedList<Character> queue = new LinkedList<>();
        StringBuilder ans = new StringBuilder();

        // add those characters who have indegree zero
        for (char ch : indegree.keySet()) {
            if (indegree.get(ch) == 0)
                queue.addLast(ch);
        }

        int count = 0;
        while (queue.size() != 0) {
            Character rem = queue.removeFirst();
            ans.append(rem);
            count++;

            if (map.containsKey(rem) == true) {
                HashSet<Character> nbrs = map.get(rem);

                for (char nbr : nbrs) {

                    indegree.put(nbr, indegree.get(nbr) - 1);
                    if (indegree.get(nbr) == 0) {
                        queue.addLast(nbr);
                    }
                }
            }
        }
        if (count == indegree.size())
            return ans.toString();

        return "";
    }

}

15) Graph valid tree


class Solution {
    /**
     * @param n:     An integer
     * @param edges: a list of undirected edges
     * @return: true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // If there is no graph to traverse, we will return true
        if (n == 0) {
            return true;
        }
        
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        
        // Create an adjacency list of an undirected graph
        for (int[] edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            adjacencyList.get(node1).add(node2);
            adjacencyList.get(node2).add(node1);
        }
        
        Set<Integer> visitedVertices = new HashSet<>();
        
        // Call the depth-first search helper method
        //we have taken initial node as 0 because we know that nodes are from 0 to n-1
        return depthFirstSearch(adjacencyList, visitedVertices, 0, -1) && n == visitedVertices.size();
    }
    
    private boolean depthFirstSearch(List<List<Integer>> adjacencyList, Set<Integer> visitedVertices, int nodeForDepthFirstSearchTraversal, int previousNode) {
        if (visitedVertices.contains(nodeForDepthFirstSearchTraversal)) {
            // If the current node is in the set of visited vertices, return false
            return false;
        }
        
        visitedVertices.add(nodeForDepthFirstSearchTraversal); // Add the current node to the visited vertices set
        
        for (int neighbor : adjacencyList.get(nodeForDepthFirstSearchTraversal)) {
            if (neighbor == previousNode) {
                // Do not apply DFS to the parent (previous) node
                continue;
            }
            
            // If the below condition returns false, it means there is a cycle, so return false
            if (!depthFirstSearch(adjacencyList, visitedVertices, neighbor, nodeForDepthFirstSearchTraversal)) {
                return false;
            }
        }
        
        // If there is no cycle, return true
        return true;
    }
}

16) Number of connect component in an undirected graph

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Java {
    private static int[] parent;
    private static int[] rank;

    public static int numberOfLooselyConnectedComponents(int n, List<List<Integer>> edges) {
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }

        int count = n;

        for (List<Integer> edge : edges) {
            int node1 = edge.get(0);
            int node2 = edge.get(1);

            count -= unionFind(node1, node2);
        }

        return count;
    }

    private static int unionFind(int node1, int node2) {
        int rootParentOfNode1 = findRootParent(node1);
        int rootParentOfNode2 = findRootParent(node2);

        if (rootParentOfNode1 == rootParentOfNode2) {
            return 0;
        }

        if (rank[rootParentOfNode1] < rank[rootParentOfNode2]) {
            parent[rootParentOfNode1] = rootParentOfNode2;
            rank[rootParentOfNode2] += rank[rootParentOfNode1];
        } else {
            parent[rootParentOfNode2] = rootParentOfNode1;
            rank[rootParentOfNode1] += rank[rootParentOfNode2];
        }

        return 1;
    }

    private static int findRootParent(int node) {
        int result = node;

        while (result != parent[result]) {
            parent[result] = parent[parent[result]];
            result = parent[result];
        }

        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> edges = new ArrayList<>();
        edges.add(Arrays.asList(0, 1));
        edges.add(Arrays.asList(1, 2));
        edges.add(Arrays.asList(3, 4));
        edges.add(Arrays.asList(2, 4));
        edges.add(Arrays.asList(5, 6));
        edges.add(Arrays.asList(4, 4));
        edges.add(Arrays.asList(5, 6));


        int n = 7;
        int componentCount = numberOfLooselyConnectedComponents(n, edges);

        System.out.println("Number of components: " + componentCount);
    }
}



17) Longest consecutive sequence

import java.util.Arrays;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = Arrays.stream(nums)
                .boxed()
                .collect(Collectors.toSet());

        AtomicInteger longestConsecutiveArraySize = new AtomicInteger(0);

        if (set.size() == 1) return 1;
        if (set.isEmpty()) return 0;

        set.parallelStream().forEach(each -> {
            if (!set.contains(each - 1)) {
                int consecutiveArraySizeCount = 1;
                int currentElement = each;

                while (set.contains(currentElement + 1)) {
                    consecutiveArraySizeCount++;
                    currentElement++;
                }

                // if we would have used simple integer then it would have thrown this error

                /*
                
                
                Line 27: error: local variables referenced from a lambda expression must be final or effectively final
                    longestConsecutiveArraySize=Math.max(longestConsecutiveArraySize,consecutiveArraySizeCount);
                                                         ^
                Line 27: error: local variables referenced from a lambda expression must be final or effectively final
                    longestConsecutiveArraySize=Math.max(longestConsecutiveArraySize,consecutiveArraySizeCount);
                    ^
                 */
                longestConsecutiveArraySize.set(Math.max(longestConsecutiveArraySize.get(), consecutiveArraySizeCount));
            }
        });

        return longestConsecutiveArraySize.get();
    }
}



18) Clone graph

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return null;
        // create a hashmap that indicates, node value of original node has an object created Copy of the type Node
        Map<Integer, Node>map=new HashMap<>();

        return cloneGraph(node, map);
    }

    private Node cloneGraph(Node node, Map<Integer, Node> map){

        if(map.containsKey(node.val)) return map.get(node.val);

        Node copy=new Node(node.val);
        map.put(node.val,copy);
        for(Node neighbor: node.neighbors) copy.neighbors.add(cloneGraph(neighbor, map));
return copy;
    }
}


19) Maximum depth of a binary tree

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDepth(TreeNode root) {
        // Using switch statement to choose between recursive and iterative approach
        String approach="iterative";
        switch (approach) {
            case "recursive":
                return maxDepthRecursive(root);
            case "iterative":
                return maxDepthIterative(root);
            default:
                throw new IllegalArgumentException("Invalid approach specified");
        }
    }
    
    // Recursive approach
    private int maxDepthRecursive(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepthRecursive(root.left), maxDepthRecursive(root.right)) + 1;
    }
    
    // Iterative approach
    private int maxDepthIterative(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            depth++;
        }
        
        return depth;
    }
}


20) Same tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode firstT, TreeNode q) {
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        if(p.val!=q.val) return false;
    
       return isSameTree(p.right, q.right)&&isSameTree(p.left, q.left); 
    }
}

21) Invert a binary tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {

   if(Objects.isNull(root)) return root;
   
   invertTree(root.left);
   invertTree(root.right);

    TreeNode temporary=root.left;
    root.left=root.right;
    root.right=temporary;

   return root;
    }
}


22) Unique paths


class Solution {
    public int uniquePaths(int m, int n) {
        
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++) dp[i][0]=1; // initialize the leftmost columns by 1 as there is only 1 way 
        for(int i=0;i<n;i++) dp[0][i]=1; // initalize the topmost row by 1 as tehre is only 1 way
        for(int i=1;i<m;i++)for(int j=1;j<n;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];// traverse all the columns
        }
        return dp[m-1][n-1];
    }
}

23) Combination sum 4

class Solution {

    Map<Integer, Integer> map=new HashMap<>(); // key would be the target value and value would be sum of combination count
    public int combinationSum4(int[] nums, int target) {
          return combinationSum4Utility(nums, target);
        }


    private int combinationSum4Utility(int[] nums, int target){

        if(map.containsKey(target)) return map.get(target);
        if(target==0) return 1;
        else if(target<0) return 0;
        else{
                int possibleWays=0;
                for(int element: nums) possibleWays+=combinationSum4Utility(nums, target-element);
                map.put(target, possibleWays);
                return possibleWays;
        }
    }
}

24) Combination sum

/**
* CombinationSum problem is the principle of backtracking
*
* 1) maintain the current state
* 2) Loop through all the possible sample set
* 3) Add new element from the sampleset 
* 4) Recursively invoke for the next entry
* 5) Remove the last element that was added in the sample set
*
* @param  candidates[] number of elements in the array
* @param  target sum that we want to achieve
* @return      returns the list of lists that sums to the target
*/

class Solution {
 
    List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0) return result;
        combinationSumUtility(candidates, target, 0,new ArrayList<Integer>(),0);
        return result;
    }  

  private void combinationSumUtility(
        int[] candidates,
        int target, 
        int currSum, // current sum that we are currently at 
        List<Integer> subList, // initially no element has been added to it 
        int index// index over which we are currently looking for 
    )
   {
      if((index>=candidates.length)||(currSum>target)) return;
      if(currSum==target) {
          result.add(new ArrayList<>(subList));
          return;
      }
      for(int i=index;i<candidates.length;i++){
          subList.add(candidates[i]);
          combinationSumUtility(candidates, target, currSum + candidates[i],subList, i);
          subList.remove(subList.size()-1);
      }

  }

}

25) Longest common subsequence

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {

        int len1=text1.length();
        int len2=text2.length();

        if(text1.equals(text2)) return len1;

        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){
                                                            
            if(text1.charAt(i-1)==text2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
        }

return dp[len1][len2];
    }
}

26) Longest increasing subsequence


import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] lis = new int[nums.length];
        Arrays.fill(lis, 1); // Initialize lis array with 1 as the minimum length of LIS for each element is 1

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        Arrays.sort(lis);
        return lis[nums.length - 1];
    }
}


27) Word break problem

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
          // store the worddict in a set
        Set<String> word_dictionary_set = new HashSet<>(wordDict);
        
        // create a `dp` array of size s.length()
        boolean[] dp = new boolean[s.length() + 1];
        
        // only the first index of the `dp` array is kept as True, 
       // since the null string will 
       // always be present in the dictionary.
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                
                // check if dp[j] is True, and if it is True,
                // also check if the substring `s[i:j]` is
                // present in the dictionary or not.
                if (dp[j] && word_dictionary_set.contains(s.substring(j, i))) {
                    
                    // If `s[i:j]` is present,
                   // mark `dp[i]` as `True` 
                   // and break from the loop 
                    dp[i] = true;
                    break;
                }
            }
        }
        
        //  Return the value present at the 
        //  nth index of the `dp` array, either true or false
        for(boolean i: dp) System.out.println(i);
        return dp[s.length()];
    }
}



28) Coin change


class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] != Integer.MAX_VALUE ? dp[amount] : -1;
    }
}


29) Climbing Stairs

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}


30) Course schedule


import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Step 1: Create an adjacency list to represent the graph
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }

        // Step 2: Populate the adjacency list with prerequisite relationships
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
        }

        // Step 3: Initialize boolean arrays for visited nodes and nodes in the current path
        boolean[] visited = new boolean[numCourses];
        boolean[] inStack = new boolean[numCourses];

        // Step 4: Iterate over each course and perform a depth-first search
        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, adj, visited, inStack)) {
                return false;
            }
        }
        return true;
    }

    // Depth-first search (DFS) function
    private boolean dfs(int node, List<List<Integer>> adj, boolean[] visited, boolean[] inStack) {
        // Step 5: Check if the current node is already in the current path
        if (inStack[node]) {
            return true; // A cycle is detected
        }
        if (visited[node]) {
            return false; // No cycle in the current path, already visited
        }

        visited[node] = true; // Mark the current node as visited
        inStack[node] = true; // Add the current node to the current path

        // Step 8: Iterate over neighbors and recursively call the DFS function
        for (int neighbor : adj.get(node)) {
            if (dfs(neighbor, adj, visited, inStack)) {
                return true; // A cycle is detected in the neighbors
            }
        }

        inStack[node] = false; // Remove the current node from the current path
        return false; // No cycle found in the current path
    }
}


31) Pacific atlantic water flow

 import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> ans = new ArrayList<>();

        int m = heights.length;
        int n = heights[0].length;

        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        // Traverse the first and last rows
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacific, heights, Integer.MIN_VALUE);
            dfs(m - 1, j, atlantic, heights, Integer.MIN_VALUE);
        }

        // Traverse the first and last columns
        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacific, heights, Integer.MIN_VALUE);
            dfs(i, n - 1, atlantic, heights, Integer.MIN_VALUE);
        }

        // Check the cells that can reach both the Pacific and Atlantic oceans
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> indexes = new ArrayList<>();
                    indexes.add(i);
                    indexes.add(j);
                    ans.add(indexes);
                }
            }
        }
        return ans;
    }

    private void dfs(int i, int j, boolean[][] canReach, int[][] matrix, int prevHeight) {
        int m = matrix.length;
        int n = matrix[0].length;

        // Check for out of bounds conditions or if the cell has already been visited
        if (i < 0 || j < 0 || i >= m || j >= n || canReach[i][j] || matrix[i][j] < prevHeight)
            return;

        // Mark the cell as reachable
        canReach[i][j] = true;

        // Recursively explore all four directions
        dfs(i - 1, j, canReach, matrix, matrix[i][j]); // Up
        dfs(i + 1, j, canReach, matrix, matrix[i][j]); // Down
        dfs(i, j - 1, canReach, matrix, matrix[i][j]); // Left
        dfs(i, j + 1, canReach, matrix, matrix[i][j]); // Right
    }
}



32) Number of islands

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0; // Variable to store the result (number of islands)
        
        // Iterate through each cell in the grid
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // If the cell contains '1', it is part of an island
                if (grid[i][j] - '0' == 1) {
                    res++; // Increment the island count
                    dfs(grid, i, j); // Call the depth-first search function to mark all connected cells as visited
                }
            }
        }
        
        return res; // Return the number of islands
    }
    
    // Depth-first search function to mark all connected cells as visited
    void dfs(char[][] grid, int i, int j) {
        // Check if the current cell is within the grid boundaries and contains '1'
        if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] - '0' == 1) {
            grid[i][j] = '0'; // Mark the current cell as visited by changing its value to '0'
            
            // Recursively call dfs on the adjacent cells (up, down, left, right)
            dfs(grid, i + 1, j); // Down
            dfs(grid, i - 1, j); // Up
            dfs(grid, i, j + 1); // Right
            dfs(grid, i, j - 1); // Left
        }
    }
}



32) Binary tree level order traversal


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (Objects.isNull(root)) return result;

        Queue<TreeNode> levelNodes = new LinkedList<>();
        levelNodes.add(root);

        while (!levelNodes.isEmpty()) {
            int levelSize = levelNodes.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {   
                TreeNode current = levelNodes.poll();
                currentLevel.add(current.val);

                if (Objects.nonNull(current.left)) {
                    levelNodes.add(current.left);
                }

                if (Objects.nonNull(current.right)) {
                    levelNodes.add(current.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }
}


33) Serialize and deserialize the binary tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
// Serialize
public String serialize(TreeNode root) {
    // Check if the current node is null
    if (root == null) {
        // If it is null, return "null," to represent a null node
        return "null,";
    }
    // Serialize the left subtree recursively
    String leftSerialized = serialize(root.left);
    // Serialize the right subtree recursively
    String rightSerialized = serialize(root.right);
    // Combine the current node value, left subtree serialization, and right subtree serialization
    return root.val + "," + leftSerialized + rightSerialized;
}

// Deserialize
public TreeNode deserialize(String data) {
    // Split the serialized data by commas and create a queue to process nodes
    Queue<String> nodesLeft = new LinkedList<>(Arrays.asList(data.split(",")));
    // Start the deserialization process by calling the helper function
    return deserializeHelper(nodesLeft);
}

// Helper function for deserialization
public TreeNode deserializeHelper(Queue<String> nodesLeft) {
    // Dequeue the next value from the queue
    String valueForNode = nodesLeft.poll();
    // If the value represents a null node, return null
    if (valueForNode.equals("null")) {
        return null;
    }
    // Create a new TreeNode with the parsed integer value
    TreeNode newNode = new TreeNode(Integer.parseInt(valueForNode));
    // Recursively deserialize the left subtree and set it as the left child
    newNode.left = deserializeHelper(nodesLeft);
    // Recursively deserialize the right subtree and set it as the right child
    newNode.right = deserializeHelper(nodesLeft);
    // Return the current node
    return newNode;
}

// Example:
// Let's use the binary tree:     1
//                              /   \
//                             2     3
//                                  / \
//                                 4   5

// Serialization:
// - serialize(root) is called with the root node (value 1)
//   - serialize(root.left) is called with the left subtree (node with value 2)
//     - serialize(null) is called for the left child of node 2
//     - serialize(null) is called for the right child of node 2
//   - serialize(root.right) is called with the right subtree (node with value 3)
//     - serialize(root.left) is called with the left subtree (node with value 4)
//       - serialize(null) is called for the left child of node 4
//       - serialize(null) is called for the right child of node 4
//     - serialize(root.right) is called with the right subtree (node with value 5)
//       - serialize(null) is called for the left child of node 5
//       - serialize(null) is called for the right child of node 5
// - The serialized result is "1,2,null,null,3,4,null,null,5,null,null,"

// Deserialization:
// - deserialize("1,2,null,null,3,4,null,null,5,null,null,") is called
// - deserializeHelper is called with the queue ["1", "2", "null", "null", "3", "4", "null", "null", "5", "null", "null"]
//   - Dequeue "1" and create a node with value 1
//   - Recursively call deserializeHelper for the left subtree
//     - Dequeue "2" and create a node with value 2
//     - Recursively call deserializeHelper for the left and right children of node 2 (both null)
//   - Recursively call deserializeHelper for the right subtree
//     - Dequeue "3" and create a node with value 3
//     - Recursively call deserializeHelper for the left subtree
//       - Dequeue "4" and create a node with value 4
//       - Recursively call deserializeHelper for the left and right children of node 4 (both null)
//     - Recursively call deserializeHelper for the right subtree
//       - Dequeue "5" and create a node with value 5
//       - Recursively call deserializeHelper for the left and right children of node 5 (both null)
// - The binary tree is successfully deserialized, and the root node with value 1 is returned

}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

34) Implement trie

class Trie {

    private TrieNode root;
    private class TrieNode{
        private TrieNode[] children = null;
        private boolean isWord;

        public TrieNode(){
            children = new TrieNode[26];
        }
    }
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode it = root;
        for(char c :  word.toCharArray()) {
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] ==null){
                it.children[indexInTrieNode] = new TrieNode();
            }
            it = it.children[indexInTrieNode];
        }
        it.isWord = true;
    }



    public boolean search(String word) {
        TrieNode it = root;
        for(char c : word.toCharArray()){
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] == null){
                // no node was found
                return false;
            } else{
                it = it.children[indexInTrieNode];
            }
        }
        return it.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode it = root;
        for(char c : prefix.toCharArray()){
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] == null){
                return false;
            } else{
                it = it.children[indexInTrieNode];
            }
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

35) Word Search 2

class Solution {

    private class TrieNode {
        private TrieNode[] children;
        private String word;
        TrieNode(){
            children = new TrieNode[26];
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        int m= board.length, n = board[0].length;

        // System.out.println(" Value is " + root.children['o' -'c']);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dfs(board,  i, j, root, res);
            }
        }
        return res;
    }

    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == ';' || p.children[c - 'a'] == null) return;
        p = p.children[c - 'a'];
        if (p.word != null) {   // found one
            res.add(p.word);
            p.word = null;     // de-duplicate
        }

        board[i][j] = ';';
        if (i > 0) dfs(board, i - 1, j ,p, res);
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res);
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
        board[i][j] = c;
    }


    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.children[i] == null) p.children[i] = new TrieNode();
                p = p.children[i];
            }
            p.word = w;
        }
        return root;
    }

}

36) Subtree of another tree


class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSameTree(root, subRoot)) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (root.val != subRoot.val) return false;
        return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }
}

37) Kth smallest element in BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        return kthSmallestElementInorder(root, k).val;
    }

    public TreeNode kthSmallestElementInorder(TreeNode root, int k) {
        if (root == null) return null;

        TreeNode left = kthSmallestElementInorder(root.left, k);

        if (left != null) return left;

        count++;
        if (count == k) return root;

        return kthSmallestElementInorder(root.right, k);
    }
}


38) Implement trie

class Trie {

    private TrieNode root;
    private class TrieNode{
        private TrieNode[] children = null;
        private boolean isWord;

        public TrieNode(){
            children = new TrieNode[26];
        }
    }
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode it = root;
        for(char c :  word.toCharArray()) {
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] ==null){
                it.children[indexInTrieNode] = new TrieNode();
            }
            it = it.children[indexInTrieNode];
        }
        it.isWord = true;
    }



    public boolean search(String word) {
        TrieNode it = root;
        for(char c : word.toCharArray()){
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] == null){
                // no node was found
                return false;
            } else{
                it = it.children[indexInTrieNode];
            }
        }
        return it.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode it = root;
        for(char c : prefix.toCharArray()){
            int indexInTrieNode = c - 'a';
            if(it.children[indexInTrieNode] == null){
                return false;
            } else{
                it = it.children[indexInTrieNode];
            }
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

39) Add and serch word

class WordDictionary {

    private class TrieNode {
        private TrieNode[] children = null;
        boolean isLeaf;

        public TrieNode(){
            children = new TrieNode[26];
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {

        TrieNode it = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            int index = c -'a';
            if(it.children[index]==null){
                TrieNode newNode = new TrieNode();
                it.children[index] = newNode;
            }
            it = it.children[index];
        }
        it.isLeaf = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return searchHelper(word, 0, root);
    }

    private boolean searchHelper(String word, int sIndex, TrieNode root){
        if(word.length()==sIndex){
            return root.isLeaf;
        }

        char c = word.charAt(sIndex);
        if(c=='.'){
            for(int i=0;i<26;i++){
                if(root.children[i]!=null && searchHelper(word, sIndex+1, root.children[i])){
                    return true;
                }
            }

        } else {
            int index = c -'a';
            if(root.children[index]!=null && searchHelper(word, sIndex+1, root.children[index])){
                return true;
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

40) Validate binary search tree


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class ValidateBinarySearchTree {
    // TC: O(n)
    // SC:Height of tree
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }

    private boolean helper(TreeNode root, long min, long max){
        if(root == null){
            return true;
        }
        if(root.val<=min || root.val>=max){
            return false;
        }

        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}

41) Construct Binary Tree from Preorder and Inorder Traversal


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;

        TreeNode root = new TreeNode(preorder[0]);
        int mid = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (preorder[0] == inorder[i]) mid = i;
        }

        root.left =
            buildTree(
                Arrays.copyOfRange(preorder, 1, mid + 1),
                Arrays.copyOfRange(inorder, 0, mid)
            );
        root.right =
            buildTree(
                Arrays.copyOfRange(preorder, mid + 1, preorder.length),
                Arrays.copyOfRange(inorder, mid + 1, inorder.length)
            );

        return root;
    }
}

42) Lowest common ancestor of a binary search tree


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {

    public TreeNode lowestCommonAncestor(
        TreeNode root,
        TreeNode p,
        TreeNode q
    ) {
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(
            root.right,
            p,
            q
        );
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(
            root.left,
            p,
            q
        );
        return root;
    }
}

43) Two sum

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> valuesAndIndexes = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int remainingAmount = target - nums[i];
            if (valuesAndIndexes.containsKey(remainingAmount)) {
                return new int[]{valuesAndIndexes.get(remainingAmount), i};
            }    
            valuesAndIndexes.put(nums[i], i);
        }
   
        throw new IllegalArgumentException("No two sum solution");
    }
}


44) Encode and Decode Strings (https://www.lintcode.com/problem/659/)


public class Solution {
    /**
     * @param strs a list of strings
     * @return encodes a list of strings to a single string.
     */
    public String encode(List<String> strs) {
        // Write your code here
        StringBuilder ans = new StringBuilder();
        for (String s : strs) {
            for (char c : s.toCharArray()) {
                if (c == ':') {                  // : itself
                    ans.append("::");
                } else {                         //ordinary character
                    ans.append(c);
                }
            }
            ans.append(":;");                    // ; connector
        }
        return ans.toString();
    }

    /**
     * @param str a string
     * @return dcodes a single string to a list of strings
     */
    public List<String> decode(String str) {
        // Write your code here
        List<String> ans = new ArrayList<>();
        char[] sc = str.toCharArray();
        StringBuilder item = new StringBuilder();
        int i = 0;
        while (i < str.length()) {
            if (sc[i] == ':') {                  //escape
                if (sc[i + 1] == ';') {          // ; connector
                    ans.add(item.toString());
                    item = new StringBuilder();
                    i += 2;
                } else {                         // : itself
                    item.append(sc[i + 1]);
                    i += 2;
                }
            } else {                             //ordinary character
                item.append(sc[i]);
                i += 1;
            }
        }
        return ans;
    }
}

45) Longest substring without repeating characters

class Solution {
    public int lengthOfLongestSubstring(String S) {
        int startPointer=0;
        int endPointer=0;
        int max=0;


        HashSet<Character> hashSet=new HashSet<Character>();

        while(endPointer<S.length()){

            if(!hashSet.contains(S.charAt(endPointer))){
                hashSet.add(S.charAt(endPointer));
                endPointer++;
                max=Math.max(hashSet.size(),max);
            }
            else{
                hashSet.remove(S.charAt(startPointer));
                startPointer++;
            }

        }
    return max;

    }
}

46) Lonmgest repeating character replacement


class Solution {
    public int characterReplacement(String s, int k) {
        return longest(s, k);        
    }
    static int longest(String s, int k){
 


        int N=s.length();

        int [] charCount=new int[26];

        int windowStart=0;
        int maxLength=0;
        int maxCount=0;
        for(int windowEnd=0;windowEnd<N; windowEnd++){


                charCount[s.charAt(windowEnd)-'A']++; // shows which characters are thgere in the window and their qantities

                int currentCharCount=charCount[s.charAt(windowEnd)-'A'];

                maxCount=Math.max(maxCount, currentCharCount);
                

                // Now in which case will we shift the window to the right

                while(windowEnd-windowStart-maxCount+1>k){ // windowEnd-windowStart-maxcount gives us the usual unmodified string winodow of repeating characters but then we are comparing it with the k elements that we can modify ourselves because we have access to modify k more elements and make them the same element that that was previously there in the window
                        // its then we shift the window with the hope that we will find a greater max count
                        charCount[s.charAt(windowStart)-'A']--;
                        windowStart++;



                }


            maxLength=Math.max(maxLength,windowEnd-windowStart+1);
        } 
return maxLength;

    }}

47) Longest palindromic substring


class Solution {
    public String longestPalindrome(String s) {
         
 if (Objects.isNull(s) || s.length()<1) return ""; // if the string is empty or with just one element
        int start=0; // start of index
        int end=0;  // end of index


        for(int i=0; i<s.length(); i++){
            // after every element traversal we will check if considering that element as center is ther ea liongest palkindromic substring
            // there are two possibilities as if the number of elements in the palindrome are odd then there will be one element in the center while comapering right most and leftmost element and the usual case
            int len1=checkForPalindromeFromTheMiddleElement(s,i,i);
            int len2=checkForPalindromeFromTheMiddleElement(s,i,i+1);
            
            int len=Math.max(len1, len2);
 
            if(len>end-start){ // now as we know the length of the palindrome we will go back half the lenght to find start index
                start=i-(len-1)/2; 
                // will will go front half the lenght toi find the end index of the longest palindrome presently
                end=i+len/2;
            }
        }  
        return s.substring(start,end+1);    
    }

      public int  checkForPalindromeFromTheMiddleElement(String s, int left, int right){
            
                if(s==null || left> right) return 0;

                while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){

                    left--;
                    right++;

                }

                return right-left-1;

     }
}

48) Palindromic substring


class Solution {

        int result=0;
    public int countSubstrings(String s) {

        for( int i=0;i<s.length();i++){
            checkForPalindromeFromTheMiddleElement(s, i, i);
            checkForPalindromeFromTheMiddleElement(s, i, i+1);
        }
        return result;

    }
      public void  checkForPalindromeFromTheMiddleElement(String s, int left, int right){
            
                while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
                    result++;
                    left--;
                    right++;

                }

     }
}

49) Reverse Linked List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode current=head;
        while(current!=null){
            ListNode LLNext=current.next;
            current.next=prev;
            prev=current;
            current=LLNext;
        }
        return prev;
    }
}

50) Remove Nth node from end of the list


class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null || head.next == null) return null;

    ListNode temp = new ListNode(0);
    temp.next = head;
    ListNode first = temp, second = temp;

    while (n > 0) {
        second = second.next;
        n--;
    }

    while (second.next != null) {
        second = second.next;
        first = first.next;
    }

    first.next = first.next.next;
    return temp.next;
}
}

51) Valid Palindrome

class Solution {
    public boolean isPalindrome(String s) {
       //Using two pointers
        String result="";
        for (char c : s.toCharArray())   if(Character.isDigit(c) || Character.isLetter(c)) result+=c; // just to remove unnecessary punctuation or any other symbol
        result=result.toLowerCase();
        int start=0;
        int end=result.length()-1;
        while(start<=end){if(result.charAt(start)!=result.charAt(end)) return false; start++; end--;}
        return true;
    }
}

52) Meeting Rooms


/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: if a person could attend all meetings
     */
    public boolean canAttendMeetings(List<Interval> intervals) {
        // Write your code here

        //declare array to gather start time and end time seperately
        int[] start=new int[intervals.size()];
        int[] end=new int[intervals.size()];

        for(int i=0;i<intervals.size(); i++){
            start[i]=intervals.get(i).start;
            end[i]=intervals.get(i).end;
        }
  
        //sort two arrays
        Arrays.sort(start);
        Arrays.sort(end);

        //Compare the ends with each start to check if they would be able ot attend all meetings
        for(int i=0;i<intervals.size()-1;i++){
            if(end[i]>start[i+1]){return false;// should always be greater ethan or equal to
            }
        }

            // if all cases pass then the user would be able to attend all the meeting        
            return true; 
    }
}


@neversettlejay
Copy link
Author

neversettlejay commented Jun 18, 2023

Combination sum done.
Pending: learn and revise the backtracking principle
Link: https://www.youtube.com/watch?v=NxgNBx11A2s

@neversettlejay
Copy link
Author

Longest common subsequence done using bottom up approach.
Pending: Didn't get 100% intuition in tabulation.
Do it using other approaches too.
https://www.youtube.com/watch?v=I3Nc9ZWfgZE

@neversettlejay
Copy link
Author

neversettlejay commented Jun 24, 2023

longest increasing subsequence done using dp bottom up.
Pending: revise, do using recursion and bst method

Do from GFG course.

@neversettlejay
Copy link
Author

neversettlejay commented Jun 24, 2023

Done word break problem
Pending: revise and understand the intuition again because of the vagueness of the question.
solve using other approaches

https://www.scaler.com/topics/word-break-problem/

@neversettlejay
Copy link
Author

neversettlejay commented Jun 24, 2023

Coin change problem done.
Pending: Revise and revise the intuition.
Solve it using other approaches

https://www.youtube.com/watch?v=wTi5Mhy9HWQ

@neversettlejay
Copy link
Author

Done climbing stairs problem
pending; revise and do it using other approach if possible

@neversettlejay
Copy link
Author

Done course schedule.
Pending: Revise DFS, perform BFS

@neversettlejay
Copy link
Author

Done pacific atlantic water flow.
Beautiful question.
Pending: revise and learn dfs and implement bfs

@neversettlejay
Copy link
Author

Number of islands is easy and doable without any help. see and attempt doing it yourself.
Pending: do BFS https://www.youtube.com/watch?v=U6-X_QOwPcs

@neversettlejay
Copy link
Author

Level order binary tree done using BFS.
Pending; do using DFS , revise BFS
https://www.youtube.com/watch?v=ICpp88mcB-k

@neversettlejay
Copy link
Author

neversettlejay commented Jul 24, 2023

To - do Word search 2: https://www.youtube.com/watch?v=DDk_ljoWd28
Learn the below program

class Solution {

    private static int COLS;
    private static int ROWS;
    private Trie currentTrie;

    public List<String> findWords(char[][] board, String[] words) { // given method
        Trie root = new Trie();
        for (String word : words) {
            root.addWord(word);
        }

        ROWS = board.length;
        COLS = board[0].length;
        HashSet<String> res = new HashSet<>();
        HashSet<String> visit = new HashSet<>();

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                dfs(r, c, root, "", res, visit, board, root);
            }
        }
        return new ArrayList<>(res);
    }

    public void dfs( int r,int c,Trie node,String word, HashSet<String> res,HashSet<String> visit,char[][] board,Trie root) {
        if (
            r < 0 ||
            c < 0 ||
            r == ROWS ||
            c == COLS ||
            !node.children.containsKey(board[r][c]) ||
            node.children.get(board[r][c]).refs < 1 ||
            visit.contains(r + "-" + c)
        ) {
            return;
        }

        visit.add(r + "-" + c);
        node = node.children.get(board[r][c]);
        word += board[r][c];
        if (node.isWord) {
            node.isWord = false;
            res.add(word);
            root.removeWord(word);
        }

        dfs(r + 1, c, node, word, res, visit, board, root);
        dfs(r - 1, c, node, word, res, visit, board, root);
        dfs(r, c + 1, node, word, res, visit, board, root);
        dfs(r, c - 1, node, word, res, visit, board, root);
        visit.remove(r + "-" + c);
    }

    class Trie {

        public HashMap<Character, Trie> children;
        public boolean isWord;
        public int refs = 0;

        public Trie() {
            children = new HashMap<>();
        }

        public void addWord(String word) {
            currentTrie = this;
            currentTrie.refs += 1;
            for (int i = 0; i < word.length(); i++) {
                char currentCharacter = word.charAt(i);
                if (!currentTrie.children.containsKey(currentCharacter)) {
                    currentTrie.children.put(currentCharacter, new Trie());
                }
                currentTrie = currentTrie.children.get(currentCharacter);
                currentTrie.refs += 1;
            }
            currentTrie.isWord = true;
        }

        public void removeWord(String word) {
            currentTrie = this;
            currentTrie.refs -= 1;
            for (int i = 0; i < word.length(); i++) {
                char currentCharacter = word.charAt(i);
                if (currentTrie.children.containsKey(currentCharacter)) {
                    currentTrie = currentTrie.children.get(currentCharacter);
                    currentTrie.refs -= 1;
                }
            }
        }
    }
}

@neversettlejay
Copy link
Author

neversettlejay commented Aug 30, 2023

https://leetcode.com/problems/binary-tree-maximum-path-sum/solutions/3746689/simple-dfs-code-faster-than-91-java/

https://www.youtube.com/watch?v=mOdetMWwtoI

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max_path_sum;
    public int maxPathSum(TreeNode root) {
        max_path_sum=Integer.MIN_VALUE;
        pathSum(root);
        return max_path_sum;
    }

    public int pathSum(TreeNode node){

        if(Objects.isNull(node)) return 0;

        int left=Math.max(0,pathSum(node.left));
        int right=Math.max(0,pathSum(node.right));
    
        max_path_sum =Math.max(max_path_sum, left+right+node.val);

        return Math.max(left, right)+ node.val;
    }
}

Good dfs approach, binary tree maximum path sum try other iterative

@neversettlejay
Copy link
Author

neversettlejay commented Oct 5, 2023

Serialize and deserialize binary tree done.
Pending: revision and iterative implementation

https://www.youtube.com/watch?v=suj1ro8TIVY

@neversettlejay
Copy link
Author

neversettlejay commented Nov 1, 2023

Word search 2 done. Important question, revise using DFS though it gives TLE and Trie implementation, really important question.

Pending revision and learning, vaguely understood the approach. Still didn't understand why did we deduplicate it.

Source: https://www.youtube.com/watch?v=EsWBGoAdm4I

@neversettlejay
Copy link
Author

Subtree of another tree done. Iterative implementation left to implement. revise the recursive approach.
Reference: https://www.youtube.com/watch?v=Qk7_vGWUMMQ

@neversettlejay
Copy link
Author

Kth smallest element in BST done.

referred this resource

https://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
Pending: revision and trying it another way

@neversettlejay
Copy link
Author

Add and search word done. Implemented using trie. Revise, didn't code, just visualized.
Link: https://www.youtube.com/watch?v=99sP62PJZXc

@neversettlejay
Copy link
Author

Implement trie done. Didn't implement. Just understood how it works.
Link: https://www.youtube.com/watch?v=EsWBGoAdm4I

To do: implement trie's questions later

@neversettlejay
Copy link
Author

Validate binary search tree done.
P.S. not implemented just understood the algorithm
Reference: https://www.youtube.com/watch?v=xjuKBVJNb7A

@neversettlejay
Copy link
Author

Construct a binary tree form inorder and postorder traversal.
Easy but tricky, learn, code and practice different approaches

Tricky because you have got to know that the preorder range while making recursive calls are same as that of the mid range that we find out.
reference:

  1. https://github.com/neetcode-gh/leetcode/blob/main/java/0105-construct-binary-tree-from-preorder-and-inorder-traversal.java (neetcode)
  2. https://www.youtube.com/watch?v=GeltTz3Z1rw&pp=ygU5Y29uc3RydWN0IGJpbmFyeSB0cmVlIGZyb20gcHJlb3JkZXIgYW5kIGlub3JkZXIgdHJhdmVyc2Fs

@neversettlejay
Copy link
Author

neversettlejay commented Dec 17, 2023

Lowest common ancestor in a Binary search tree
Pending: implementation and learn, implement alternative
Reference:

  1. https://github.com/neetcode-gh/leetcode/blob/main/java/0235-lowest-common-ancestor-of-a-binary-search-tree.java
  2. https://www.youtube.com/watch?v=nEsoNjZtkiI
  3. for binary tree (Important, implement and learn this too): https://www.youtube.com/watch?v=4laAl6_L144

@neversettlejay
Copy link
Author

Two sum done
Pending: revision and different approach

@neversettlejay
Copy link
Author

Longest substring without repeating characters done.
easy to understand problem
Pending: Other approaches if any
Reference: https://www.youtube.com/watch?v=3IETreEybaA

@neversettlejay
Copy link
Author

neversettlejay commented Feb 2, 2024

Longest repeating character replacement done

Pending: doubt on how is maxLength giving right answer, revise

Reference: https://www.youtube.com/watch?v=00FmUN1pkGE&t=1s

@neversettlejay
Copy link
Author

Longest palindromic substring done.
Pending : Different approach , DP
have confusion about the fact that if it doesn't store history of start and end then how are we getting the right answer

Reference: https://www.youtube.com/watch?v=y2BD4MJqV20

@neversettlejay
Copy link
Author

Palindromic substring done using the logic of iterating and checking for palindrome from the middle.
Pending: to implement it using DP and other approaches, revision of this logic

Reference: https://www.youtube.com/watch?v=gI1771HyXu0

@neversettlejay
Copy link
Author

@neversettlejay
Copy link
Author

neversettlejay commented May 7, 2024

Remove Nth node from the end of the list

The idea here is to make a gap between two positions of the list and travel the list till the very end keeping the length/gap of the two positions/pointers the same and in the end when the pointer in the from reaches the end, the pointer behind it would be at a place that needs to be deleted so we perform linked list operations to skip one Node.

References:
https://www.youtube.com/watch?v=XVuQxVej6y8
https://github.com/neetcode-gh/leetcode/blob/main/java/0019-remove-nth-node-from-end-of-list.java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
     if (Objects.isNull(head) || Objects.isNull(head.next)) return null;
     ListNode zeroIndexNode=new ListNode(0);
     zeroIndexNode.next=head; //Joint 0 value node to the start of list
     ListNode behind=zeroIndexNode;
     ListNode front=zeroIndexNode;
     while(n>0){
        front=front.next;
        n--;
     } // create the distance equal to that of n 

     while(Objects.nonNull(front.next)){
        front=front.next;
        behind=behind.next;
     }

     behind.next=behind.next.next;
     return zeroIndexNode.next;

    }
}

@neversettlejay
Copy link
Author

Valid Palindrome done
Easy question, just go through it to revise.

Reference: https://www.youtube.com/watch?v=rYyn9Vc-dBQ

@neversettlejay
Copy link
Author

Meeting rooms 1 is easy , just logical

Reference: https://www.lintcode.com/problem/920/

https://www.youtube.com/watch?v=i2bBG7CaVxs

Pending: try optimizing it

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment