Forem: Prashant Mishra

Algo: Binary Search

Prashant Mishra — Sun, 03 May 2026 13:03:10 +0000

Example: Search in rotated sorted array II

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(target==nums[mid]) return true;
            if(nums[left]==nums[mid] && nums[mid] == nums[right]){
                left++;
                right--;
                continue;
            }
            if(nums[left]<=nums[mid]){
               if(target<nums[mid] && target>=nums[left]) right = mid-1;
               else left=  mid+1;
            }
            else {
                if(target > nums[mid] && target<= nums[right]) left = mid+1;
                else right =  mid-1;
            }

        }
        return false;
    }
}

Pattern: Permutations

Prashant Mishra — Sun, 03 May 2026 10:06:39 +0000

A Permutations is rearrangement of all the elements of the array.
Example:
Permutations

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int taken[] = new int[nums.length];
        permute(nums, taken, new ArrayList<>());
        return list;
    }
    public void permute(int nums[], int [] taken, List<Integer> l){
        if(l.size()== nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = 0;i< nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && taken[i-1]==1) continue;
            if(taken[i]==0){
                taken[i] = 1;
                l.add(nums[i]);
                permute(nums,taken,l);
                l.remove(l.size()-1);
                taken[i]=0;
            }
        }
    }
}

Example 2: Permutation II - get unique permutations

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int taken[] = new int[nums.length];
        permute(nums, taken, new ArrayList<>());
        return list;  
    }
    public void permute(int nums[], int [] taken, List<Integer> l){
        if(l.size()== nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = 0;i< nums.length;i++){
            //If previous duplicate is NOT used → skip current
            if(i>0 && nums[i]==nums[i-1] && taken[i-1]==0) continue;
            if(taken[i]==0){
                taken[i] = 1;
                l.add(nums[i]);
                permute(nums,taken,l);
                l.remove(l.size()-1);
                taken[i]=0;
            }
        }
    }
}

Pattern: DFS Algo

Prashant Mishra — Wed, 29 Apr 2026 16:54:52 +0000

Used in graph traversal where you visit all the nodes at the same level then go on visiting nodes in the next level
E.g. Shortest path in binary matrix

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]!=0) return -1;
        Queue<Node> q  = new LinkedList<>();
        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0},{1,1},{-1,-1},{-1,1},{1,-1}};
        q.add(new Node(0,0,1)); // stating point (0,0) with distance 1
        int visited[][] = new int[grid.length][grid[0].length];
        for(int vis[]: visited){
            Arrays.fill(vis, -1);
        }

        while(!q.isEmpty()){
            Node n = q.remove();
            int I = n.i;
            int J = n.j;
            int D = n.d;
            if(I == grid.length-1 && J == grid[0].length-1) return D;
            for(int dir[]: dirs){
                int i = dir[0] + I;
                int j = dir[1] + J;
                if(i<grid.length && j<grid[0].length && i>=0 && j>=0 && grid[i][j] ==0 && visited[i][j]==-1){
                    visited[i][j] = 1;
                    q.add(new Node(i,j, D+1));
                }
            }
        }
        return -1;
    }
}
class Node{
    int i;
    int j;
    int d;
    public Node(int i, int j, int d){
        this.i  =i;
        this.j = j;
        this.d = d;
    }
}

Solved using Dijkstra's single source shortest path- it is Not recommended as it is not that efficient in this case as each step has weight i.e 1

Pattern: Matrix Manupulation

Prashant Mishra — Mon, 27 Apr 2026 16:27:18 +0000

Matrix manipulation involves, matrix traversal and manipulation based on matrix properties
Example: Rotate Image

class Solution {
    public void rotate(int[][] matrix) {
        //replacing rows with columns
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<i;j++){
                swap(i,j,m,n,matrix);
            }
        }

        //swapping the columns
        int p = 0; int q = n-1;
        while(p<q){
            for(int i =0;i<m;i++){
                int temp = matrix[i][p];
                matrix[i][p] = matrix[i][q];
                matrix[i][q] = temp;
            }
            p++;
            q--;
        }
    }
    public void swap(int i, int j, int m ,int n, int matrix[][]){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
}

Pattern: Reverse LinkedList

Prashant Mishra — Mon, 27 Apr 2026 16:16:14 +0000

Reverse a LinkedList

/**
 * 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;
        while(head!=null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

Pattern:Cyclic Sort

Prashant Mishra — Mon, 27 Apr 2026 16:06:56 +0000

Cyclic Sort: Instead of comparing elements like normal sorting, you place each number directly at its correct index.

Example: Find all the numbers disappeared in an array

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {

        int  i =0;
        int n = nums.length;
        while(i<n){
            int correctIndex = nums[i]-1;
            //ignore all the out of bound indexes
            if(correctIndex < nums.length && correctIndex >=0 && nums[i] != nums[correctIndex]){
                swap(i,correctIndex,nums);
            }
            else i++;
        }
        List<Integer> list = new ArrayList<>();
        for(i =0;i<nums.length;i++){
            if((i+1)!=nums[i]) list.add(i+1);
        }
        return list;
    }
    public void swap(int i, int j, int arr[]){
        int temp = arr[i];
        arr[i]= arr[j];
        arr[j] = temp;
    }
}

Pattern: Two Pointer

Prashant Mishra — Fri, 24 Apr 2026 14:39:57 +0000

Problems where we can use two pointers i,j to get to a solution in the given Array or String
Example : Two Sum II Input Arrays is Sorted
Here we have find two indices from the given array such that sum of those indices value is target (condition index1< index2)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l=  0;
        int r = numbers.length-1;
        while(l<r){
            int sum = numbers[l] + numbers[r];
            if(sum == target) return new int[]{l+1,r+1};
            else if(sum < target) l++;
            else r--;
        }
        return new int[-1];
    }
}

Pattern: sliding window (Variable window)

Prashant Mishra — Fri, 24 Apr 2026 14:17:56 +0000

Sliding window of variable size that satisfy given constraint, i.e
Finding continuous substring/subarray that satisfies the given condition.
e.g. Longest substring without repeating characters

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int r = 0;
        int size = 0;
        int arr[]  = new int[256];
        Arrays.fill(arr,-1); //intially indices of all the characters are -1

        while(r<s.length()){
            char c = s.charAt(r);
            if(arr[c]!=-1){ //seen in the past
                if(arr[c] >=l){ // if it was seen after the left index then we have a duplicate in the range of l and r we have to move the left pointer
                    l = arr[c]+1; 
                }

            }
            arr[c] = r;
            size= Math.max(size, r-l+1);
            r++;
        }
        return size;
    }
}

Pattern: Sliding window (fixed window)

Prashant Mishra — Thu, 23 Apr 2026 16:37:21 +0000

Problems that involves operations on contiguous range of substring/subarray
eg. Maximum sum subarray of size k (Fixed window of size K)

class Solution {
    public int maxSubarraySum(int[] arr, int k) {
        // Code here
        int left  =0;
        int right  =0;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        while(right<arr.length){
            if(right-left+1<k){
                sum+=arr[right];
                right++;
            }
            else{
                sum+=arr[right];
                max = Math.max(max, sum);
                sum = sum-arr[left];
                left++;
                right++;
            }
        }
        return  max;
    }
}

Pattern: Prefix sum

Prashant Mishra — Wed, 22 Apr 2026 16:58:31 +0000

Prefix sum: involves storing sum/product upto each index for quick access/lookup for range queries
e.g. Product of Array Except Self

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int a[] =  new int[nums.length];
        int b[] = new int[nums.length];
        a[0] = nums[0];
        b[nums.length-1] = nums[nums.length-1];
        for(int i =1;i< nums.length;i++){
            a[i]  = a[i-1]*nums[i];
        }
        for(int i  = nums.length-2;i>=0;i--){
            b[i] = nums[i]*b[i+1];
        }
        System.out.println();
        for(int i = 0;i< nums.length;i++){
            nums[i] = (i-1 >=0 ? a[i-1] : 1) * (i+1 <=nums.length-1 ? b[i+1] : 1); 
        }
        return nums;
    }
}

Pattern: Overlapping intervals

Prashant Mishra — Wed, 22 Apr 2026 10:30:42 +0000

Given list of (start and end time/sequence) we have to merge the overlapping intervals.
eg: Merge Overlapping intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b)-> a[0] - b[0]);// sort by starting time
        List<List<Integer>> list  = new ArrayList<>();
        int start = intervals[0][0]; int end = intervals[0][1];
        for(int i =1;i< intervals.length;i++){
            if(end >= intervals[i][0]){
                end = Math.max(end, intervals[i][1]);
                continue;
            }
            else{
                List<Integer> l = new ArrayList<>();
                l.add(start);
                l.add(end);
                list.add(l);
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        List<Integer> l = new ArrayList<>();
        l.add(start);
        l.add(end);
        list.add(l);
        int result[][] = new int[list.size()][2];
        for(int i = 0;i< list.size();i++){
            result[i][0] = list.get(i).get(0);
            result[i][1] = list.get(i).get(1);
        }
        return result;
    }
}

Pattern: Slow fast pointer

Prashant Mishra — Wed, 22 Apr 2026 09:06:08 +0000

If we use slow and fast pointer at some point fast pointer and slow pointer will point to the same node.
Example: Detect cycle in the graph

public class Solution {
    public boolean hasCycle(ListNode head) {
         if(head ==null || head.next ==null) return false;
        ListNode slow = head;
        ListNode fast = slow.next;
        while(fast!=null){
            if(slow ==fast) return true;
            slow = slow.next;
            fast = fast.next ==null ? null : fast.next.next;
        }
        return false;
    }
}