Java SSE Ultimate Learning Guide

Approach

One-pass map value→index; probe for complement.

Easy Algorithm

1. Map value→index.
2. If complement seen return [j,i] else store.

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course's twoSum snippet. Solution is nested so the
 * whole program fits in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * One-pass hash map solution: for each number, look up whether its complement
     * (target - number) was already seen; if so return both indices.
     */
    static class Solution {
public int[] twoSum(int[] nums,int target){Map<Integer,Integer> m=new HashMap<>();
for(int i=0;i<nums.length;i++){Integer j=m.get(target-nums[i]);if(j!=null)return new int[]{j,i};m.put(nums[i],i);}
throw new IllegalArgumentException("none");}
  public static void main(String[] args) {
    System.out.println(Arrays.toString(new Solution().twoSum(new int[]{2,7,11,15},9)));
  }
    }

    public static void main(String[] args) {
        // Lesson example: 2 + 7 = 9, so the indices are [0, 1]
        Solution.main(args);
        // Complement found later in the array: 3 + 4 = 7 at indices [1, 2]
        System.out.println(Arrays.toString(new Solution().twoSum(new int[]{5, 3, 4}, 7)));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,7,11,15],9 → [0,1]

Also asked: Amazon OA, Target

Approach

Left products into ans; multiply running right product.

Easy Algorithm

1. Left pass into ans.
2. Right pass multiply suffix.

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course's productExceptSelf snippet. Solution is nested so the
 * whole program fits in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Builds the answer in two passes without division: first each slot holds the product
     * of everything to its left, then a running product of everything to its right is multiplied in.
     */
    static class Solution {
public int[] productExceptSelf(int[] nums){int n=nums.length;int[] a=new int[n];a[0]=1;
for(int i=1;i<n;i++)a[i]=a[i-1]*nums[i-1];int r=1;for(int i=n-1;i>=0;i--){a[i]*=r;r*=nums[i];}return a;}
  public static void main(String[] args) {
    System.out.println(Arrays.toString(new Solution().productExceptSelf(new int[]{1,2,3,4})));
  }
    }

    public static void main(String[] args) {
        // Lesson example: [24, 12, 8, 6]
        Solution.main(args);
        // A zero makes every other slot 0 and its own slot the product of the rest: [0, 6, 0, 0]
        System.out.println(Arrays.toString(new Solution().productExceptSelf(new int[]{2, 0, 3, 1})));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,2,3,4]→[24,12,8,6]

Also asked: Amazon

Approach

Ends inward; advance the shorter side.

Easy Algorithm

1. L,R ends; track best.
2. Move shorter pointer.

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course snippet. Solution is nested so the whole program fits
 * in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Two-pointer scan from both ends: always move the shorter wall inward, tracking the best area.
     */
    static class Solution {
public int maxArea(int[] h){int L=0,R=h.length-1,b=0;while(L<R){b=Math.max(b,Math.min(h[L],h[R])*(R-L));if(h[L]<h[R])L++;else R--;}return b;}
  public static void main(String[] args) {
    System.out.println(new Solution().maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
  }
    }

    public static void main(String[] args) {
        // Lesson example: walls of height 8 (index 1) and 7 (index 8) give 7 * 7 = 49
        Solution.main(args);
        // A second case: two walls of height 1, one apart, hold an area of 1
        System.out.println(new Solution().maxArea(new int[]{1, 1}));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

classic heights → 49

Also asked: Amazon

Approach

Expand odd/even centers; keep best window.

Easy Algorithm

1. For each i expand(i,i) and expand(i,i+1).
2. Track max window.

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course snippet. Solution is nested so the whole program fits
 * in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Expand around each center (odd and even length) and keep the longest palindrome found.
     */
    static class Solution {
public String longestPalindrome(String s){int st=0,en=0;for(int i=0;i<s.length();i++){int[] a=ex(s,i,i),b=ex(s,i,i+1);int[] c=a[1]-a[0]>=b[1]-b[0]?a:b;if(c[1]-c[0]>en-st){st=c[0];en=c[1];}}return s.substring(st,en+1);}
int[] ex(String s,int L,int R){while(L>=0&&R<s.length()&&s.charAt(L)==s.charAt(R)){L--;R++;}return new int[]{L+1,R-1};}
  public static void main(String[] args) {
    System.out.println(new Solution().longestPalindrome("babad"));
  }
    }

    public static void main(String[] args) {
        // Lesson example: "babad" -> "bab" ("aba" is an equally long valid answer)
        Solution.main(args);
        // Even-length palindrome: "cbbd" contains "bb"
        System.out.println(new Solution().longestPalindrome("cbbd"));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

babad → bab

Also asked: Amazon, Microsoft

Approach

Sorted-char key → bucket list.

Easy Algorithm

1. key=sorted(s)
2. map key→list; return values

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course snippet. Solution is nested so the whole program fits
 * in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Groups anagrams by using each word's sorted letters as a hash map key.
     */
    static class Solution {
public List<List<String>> groupAnagrams(String[] strs){Map<String,List<String>> m=new HashMap<>();
for(String s:strs){char[] c=s.toCharArray();Arrays.sort(c);m.computeIfAbsent(new String(c),k->new ArrayList<>()).add(s);}
return new ArrayList<>(m.values());}
  public static void main(String[] args) {
    System.out.println(new Solution().groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
  }
    }

    public static void main(String[] args) {
        // Lesson example: three groups (eat/tea/ate, tan/nat, bat); the order of groups follows the HashMap
        Solution.main(args);
        // A single word forms a single group
        System.out.println(new Solution().groupAnagrams(new String[]{"a"}));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

eat/tea/ate together

Also asked: Amazon, Uber

Approach

Count letters; all counts must return to zero.

Easy Algorithm

1. length check
2. inc s / dec t; verify zeros

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course snippet. Solution is nested so the whole program fits
 * in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Compares letter counts: increment for s, decrement for t, and every count must end at zero.
     */
    static class Solution {
public boolean isAnagram(String s,String t){if(s.length()!=t.length())return false;int[] c=new int[26];
for(int i=0;i<s.length();i++){c[s.charAt(i)-'a']++;c[t.charAt(i)-'a']--;}for(int x:c)if(x!=0)return false;return true;}
  public static void main(String[] args) {
    System.out.println(new Solution().isAnagram("anagram","nagaram"));
  }
    }

    public static void main(String[] args) {
        // Lesson example: "anagram" and "nagaram" use the same letters
        Solution.main(args);
        // Different letters: "rat" and "car" are not anagrams
        System.out.println(new Solution().isAnagram("rat", "car"));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

anagram/nagaram → true

Also asked: Amazon, Target

Approach

Compact nonzeros forward; fill rest with zeroes.

Easy Algorithm

1. w=0 write nonzeros
2. fill [w..] with 0

Code (Java)

import java.util.*;

/**
 * Demo wrapper for the course snippet. Solution is nested so the whole program fits
 * in one file; the snippet's own main prints the lesson example.
 */
public class Main {
    /**
     * Two-pointer, in place: copy every non-zero forward to the write index, then fill the rest with zeroes.
     */
    static class Solution {
public int[] moveZeroes(int[] nums){int w=0;for(int x:nums)if(x!=0)nums[w++]=x;while(w<nums.length)nums[w++]=0;return nums;}
  public static void main(String[] args) {
    int[] a=new int[]{0,1,0,3,12}; System.out.println(Arrays.toString(new Solution().moveZeroes(a)));
  }
    }

    public static void main(String[] args) {
        // Lesson example: [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
        Solution.main(args);
        // Already compact: nothing to move
        System.out.println(Arrays.toString(new Solution().moveZeroes(new int[]{1, 2, 3})));
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[0,1,0,3,12]→[1,3,12,0,0]

Also asked: Amazon

Approach

Sum every positive adjacent price difference.

Easy Algorithm

1. for each ascent add delta

Code (Java)

import java.util.*;

// Main entry point for the program
public class Main {
    // Solution class for Best Time to Buy and Sell Stock II problem
    // Calculates maximum profit from unlimited buy/sell transactions
    static class Solution {
        // Original method from snippet - calculates max profit by summing all positive price differences
public int maxProfitII(int[] p){int a=0;for(int i=1;i<p.length;i++)if(p[i]>p[i-1])a+=p[i]-p[i-1];return a;}
  // Original main method from snippet - tests with sample input
  public static void main(String[] args) {
    System.out.println(new Solution().maxProfitII(new int[]{7,1,5,3,6,4}));
  }
    }
    
    // Main method to run the program and exercise the snippet
    public static void main(String[] args) {
        // Run the original test from Solution's main
        Solution.main(args);
        
        // Additional test cases to demonstrate the solution with various inputs
        Solution sol = new Solution();
        System.out.println("Additional tests:");
        System.out.println("Test 2 (increasing prices): " + sol.maxProfitII(new int[]{1,2,3,4,5})); // Expected: 4
        System.out.println("Test 3 (decreasing prices): " + sol.maxProfitII(new int[]{7,6,4,3,1})); // Expected: 0
        System.out.println("Test 4 (single price): " + sol.maxProfitII(new int[]{1})); // Expected: 0
        System.out.println("Test 5 (empty array): " + sol.maxProfitII(new int[]{})); // Expected: 0
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[7,1,5,3,6,4]→7

Also asked: Amazon

Approach

If mid > right, min is to the right; else mid or left.

Easy Algorithm

1. while lo<hi
2. branch on a[mid]>a[hi]

Code (Java)

import java.util.*;
public class Main {
  // Solution class implements binary search to find the minimum in a rotated sorted array
  static class Solution {
    public int findMin(int[] a){int lo=0,hi=a.length-1;while(lo<hi){int m=(lo+hi)/2;if(a[m]>a[hi])lo=m+1;else hi=m;}return a[lo];} // binary search loop: narrow range until min found
    public static void main(String[] args) { // demo main from the snippet
      System.out.println(new Solution().findMin(new int[]{3,4,5,1,2})); // test case: rotated array, expected 1
    }
  }
  public static void main(String[] args) {
    Solution.main(args); // run the snippet's main
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[3,4,5,1,2]→1

Also asked: Amazon, Uber

Approach

Identify sorted half; binary-search the half that can hold target.

Easy Algorithm

1. compare mid
2. shrink to feasible sorted half

Code (Java)

import java.util.*;  // Import utilities

/**
 * Main entry point for the rotated array search demo.
 */
public class Main {
    /**
     * Solution class containing the rotated sorted array search algorithm.
     * Finds target index in a rotated sorted array using binary search O(log n).
     */
    static class Solution {
public int searchRotated(int[] a,int t){int lo=0,hi=a.length-1;while(lo<=hi){int m=(lo+hi)/2;if(a[m]==t)return m;  // Binary search: compute mid, check for target
if(a[lo]<=a[m]){if(a[lo]<=t&&t<a[m])hi=m-1;else lo=m+1;}else{if(a[m]<t&&t<=a[hi])lo=m+1;else hi=m-1;}}return -1;}  // Identify sorted half and narrow search range
  public static void main(String[] args) {  // Demo main from original snippet
    System.out.println(new Solution().searchRotated(new int[]{4,5,6,7,0,1,2},0));  // Search for 0 in rotated array, prints index 4
  }
    }

    // Main entry point calls Solution.main to run the demo
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[4,5,6,7,0,1,2],0 → 4

Also asked: Amazon, Meta

Approach

DFS with start index; reuse same index to keep nondecreasing order.

Easy Algorithm

1. dfs(remain,start,path)
2. for i>=start push/recurse(i)/pop

Code (Java)

// Imports Java utility classes for collections.
import java.util.*;
// Outer main class that hosts the solution and program entry point.
public class Main {
    // Static nested class containing the combination sum algorithm (candidates may be reused).
    static class Solution {
        // Public method to find all unique combinations that sum to target; initializes result list and starts DFS.
        public List<List<Integer>> combinationSum(int[] c,int t){List<List<Integer>> res=new ArrayList<>();dfs(c,t,0,new ArrayList<>(),res);return res;}
        // Private helper method performing depth-first search with backtracking to explore combinations.
        void dfs(int[] c,int rem,int start,List<Integer> path,List<List<Integer>> res){if(rem==0){res.add(new ArrayList<>(path));return;}
        // Loop through candidates starting from index; skip if candidate exceeds remaining target; add candidate, recurse, then backtrack.
        for(int i=start;i<c.length;i++){if(c[i]>rem)continue;path.add(c[i]);dfs(c,rem-c[i],i,path,res);path.remove(path.size()-1);}}
          // Main method inside Solution class for demonstration.
          public static void main(String[] args) {
            // Demo call: prints combinations of [2,3,6,7] that sum to 7.
            System.out.println(new Solution().combinationSum(new int[]{2,3,6,7},7));
          }
    }
    // Outer program entry point; delegates to Solution.main.
    public static void main(String[] args) {
        // Calls the demonstration main method of Solution class.
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,3,6,7],7 → [[2,2,3],[7]]

Also asked: Amazon

Approach

DFS from each matching start; mark visited then restore.

Easy Algorithm

1. try each cell
2. dfs mark '#', explore 4 dirs, unmark

Code (Java)

import java.util.*; // Standard utilities import
public class Main {
    // Nested Solution class containing the word search algorithm
    static class Solution {
        public boolean exist(char[][] b,String w){for(int r=0;r<b.length;r++)for(int c=0;c<b[0].length;c++)if(dfs(b,w,0,r,c))return true;return false;} // Checks if word exists in board using DFS backtracking
        boolean dfs(char[][] b,String w,int i,int r,int c){if(i==w.length())return true;if(r<0||c<0||r>=b.length||c>=b[0].length||b[r][c]!=w.charAt(i))return false; // Depth-first search from (r,c) matching w starting at index i
        char t=b[r][c];b[r][c]='#';boolean ok=dfs(b,w,i+1,r+1,c)||dfs(b,w,i+1,r-1,c)||dfs(b,w,i+1,r,c+1)||dfs(b,w,i+1,r,c-1);b[r][c]=t;return ok;} // Mark visited, explore 4 directions, restore
          public static void main(String[] args) { // Original main method for demonstration
            System.out.println(new Solution().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}}, "ABCCED"));
          }
    }

    // Entry point: delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

ABCCED on classic board → true

Also asked: Amazon, Microsoft

Approach

dp[i]=max(dp[i-1], dp[i-2]+nums[i]); roll two variables.

Easy Algorithm

1. prev2,prev1
2. for x: cur=max(prev1, prev2+x); shift

Code (Java)

import java.util.*;

/**
 * Main class to run the House Robber solution.
 * The Solution class is nested statically as required.
 */
public class Main {
    /**
     * Solution class for the House Robber problem.
     * Computes maximum money that can be robbed without robbing adjacent houses.
     * Uses O(1) space DP with two variables.
     */
    static class Solution {
        // Original line preserved exactly as given
        public int rob(int[] a){int p2=0,p1=0;for(int x:a){int cur=Math.max(p1,p2+x);p2=p1;p1=cur;}return p1;}
        
        // Original main method preserved exactly
        public static void main(String[] args) {
            System.out.println(new Solution().rob(new int[]{1,2,3,1}));
        }
    }
    
    /**
     * Main entry point - delegates to Solution.main to exercise the snippet.
     */
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,2,3,1]→4 (1+3)

Also asked: Amazon, Airbnb

Approach

Max of rob linear range [0..n-2] and [1..n-1].

Easy Algorithm

1. if n==1 return a[0]
2. return max(robLine(0,n-2), robLine(1,n-1))

Code (Java)

import java.util.*;

// Main entry point for the House Robber II demonstration
public class Main {
    // Solution class implementing the circular House Robber algorithm
    static class Solution {
        // Robs maximum amount from circular arrangement of houses
public int rob2(int[] a){int n=a.length;if(n==1)return a[0];return Math.max(line(a,0,n-2),line(a,1,n-1));} // Computes max of two linear subproblems excluding first/last house
        // Helper for linear house robber using O(1) space DP
int line(int[] a,int L,int R){int p2=0,p1=0;for(int i=L;i<=R;i++){int cur=Math.max(p1,p2+a[i]);p2=p1;p1=cur;}return p1;} // Iterates range [L,R], maintains two previous max values
        // Tests the solution with sample input [2,3,2] expected output 3
  public static void main(String[] args) {
    System.out.println(new Solution().rob2(new int[]{2,3,2}));
  }
    }
    // Program entry point delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,3,2]→3

Also asked: Amazon

Approach

ways(n)=ways(n-1)+ways(n-2); roll two ints.

Easy Algorithm

1. a=1,b=1
2. repeat n-1 times: a,b = b, a+b

Code (Java)

import java.util.*;
public class Main {
    // Nested Solution class containing the climbing stairs algorithm
    static class Solution {
public int climbStairs(int n){int a=1,b=1;for(int i=0;i<n-1;i++){int c=a+b;a=b;b=c;}return b;}  // Fibonacci-style DP: compute ways to climb n stairs
  public static void main(String[] args) {                               // Demo entry point in Solution
    System.out.println(new Solution().climbStairs(3));                   // Prints 3 for n=3
  }
}
    // Main entry point: delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

n=3 → 3

Also asked: Amazon

Approach

dp[r][c]=dp[r-1][c]+dp[r][c-1]; use 1D rolling row.

Easy Algorithm

1. row of 1s length n
2. for each of m-1 rows: prefix-sum update

Code (Java)

import java.util.*; // Import utilities like Arrays

public class Main {
    // Solution class implementing unique paths calculation using 1D DP
    static class Solution {
        // Calculate unique paths from top-left to bottom-right in m x n grid
        public int uniquePaths(int m,int n){int[] dp=new int[n];Arrays.fill(dp,1);
        for(int r=1;r<m;r++)for(int c=1;c<n;c++)dp[c]+=dp[c-1];return dp[n-1];}
          public static void main(String[] args) {
            System.out.println(new Solution().uniquePaths(3,7));
          }
    }

    // Entry point: delegate to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

m=3,n=7 → 28

Also asked: Amazon, Google-lite

Approach

Maintain tails of active LIS piles; binary search replace.

Easy Algorithm

1. tails=[]; for x: lower_bound replace or append
2. answer=tails.size

Code (Java)

import java.util.*; // Standard utilities for List, ArrayList, Collections
public class Main {
    // Nested Solution class containing the O(n log n) LIS algorithm using patience sorting with binary search
    static class Solution {
        // Original method: computes length of longest strictly increasing subsequence
        public int lengthOfLIS(int[] nums){List<Integer> t=new ArrayList<>(); // tails of active piles
        for(int x:nums){int i=Collections.binarySearch(t,x);if(i<0)i=-(i+1);if(i==t.size())t.add(x);else t.set(i,x);}return t.size();}
        // Original main method demonstrating usage with sample input
          public static void main(String[] args) {
            System.out.println(new Solution().lengthOfLIS(new int[]{10,9,2,5,3,7,101,18})); // prints 4
          }
    }
    
    // Main entry point delegates to Solution.main to run the demo
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[10,9,2,5,3,7,101,18]→4

Also asked: Amazon, Google

Approach

dp[i][j] from prefixes; take min of insert/delete/replace.

Easy Algorithm

1. init borders as i/j
2. if equal diag else 1+min(3 ops)

Code (Java)

import java.util.*;

// Main class to run the edit distance solution
public class Main {
    // Solution class implementing Levenshtein edit distance
    static class Solution {
        public int minDistance(String a,String b){int m=a.length(),n=b.length();int[][] dp=new int[m+1][n+1]; // compute lengths and allocate DP table
        for(int i=0;i<=m;i++)dp[i][0]=i;for(int j=0;j<=n;j++)dp[0][j]=j; // initialize borders: cost of deleting/inserting all chars
        for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){ // fill DP for each prefix pair
        if(a.charAt(i-1)==b.charAt(j-1))dp[i][j]=dp[i-1][j-1]; // chars match: no extra cost, take diagonal
        else dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]));} // mismatch: 1 + min of replace, insert, delete
        return dp[m][n];} // final answer in bottom-right cell
          public static void main(String[] args) { // demo: edit distance between "horse" and "ros"
            System.out.println(new Solution().minDistance("horse","ros"));
          }
    }

    // Entry point: delegates to Solution.main for demonstration
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

horse→ros = 3

Also asked: Amazon, Google

Approach

Track best ending here; reset when negative contribution.

Easy Algorithm

1. best=cur=nums[0]
2. cur=max(x, cur+x); best=max(best,cur)

Code (Java)

import java.util.*;

// Main class to run the program
public class Main {
    // Solution class containing Kadane's algorithm for maximum subarray sum
    static class Solution {
public int maxSubArray(int[] a){int best=a[0],cur=a[0];for(int i=1;i<a.length;i++){cur=Math.max(a[i],cur+a[i]);best=Math.max(best,cur);}return best;}
  public static void main(String[] args) {
    System.out.println(new Solution().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
  }
    }

    // Main entry point that delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[-2,1,-3,4,-1,2,1,-5,4]→6

Also asked: Amazon, Target

Approach

Add all before; merge overlaps; append rest.

Easy Algorithm

1. push intervals ending before new start
2. merge while overlapping
3. append remaining

Code (Java)

import java.util.*;

// Main class to run the interval insertion program
public class Main {
    // Solution class containing the algorithm to insert and merge intervals
    static class Solution {
        // Inserts a new interval into sorted non-overlapping intervals and merges overlaps
        public int[][] insertInterval(int[][] intervals,int[] neu){List<int[]> res=new ArrayList<>();int i=0,n=intervals.length; // Initialize result list and loop variables
        while(i<n&&intervals[i][1]<neu[0])res.add(intervals[i++]); // Add all intervals ending before new interval starts
        while(i<n&&intervals[i][0]<=neu[1]){neu[0]=Math.min(neu[0],intervals[i][0]);neu[1]=Math.max(neu[1],intervals[i][1]);i++;} // Merge overlapping intervals with new interval
        res.add(neu);while(i<n)res.add(intervals[i++]);return res.toArray(new int[0][]);} // Add merged interval and append remaining intervals
        // Test the insertInterval method with a sample case
        public static void main(String[] args) {
            // Expected output: [[1,5],[6,9]] - [2,5] merges with [1,3]
            System.out.println(Arrays.deepToString(new Solution().insertInterval(new int[][]{{1,3},{6,9}}, new int[]{2,5})));
        }
    }
    // Program entry point delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[[1,3],[6,9]] + [2,5] → [[1,5],[6,9]]

Also asked: Amazon, Google

Approach

Sort by end; keep interval if start >= lastEnd else remove (count++).

Easy Algorithm

1. sort by end
2. greedy take non-overlapping; count skips

Code (Java)

import java.util.*;

/**
 * Main entry point for the interval overlap removal demo.
 * Nests the Solution class from the course snippet and delegates to its main.
 */
public class Main {
    /**
     * Solution class containing the greedy algorithm to find minimum
     * number of intervals to remove so the rest are non-overlapping.
     * Sorts intervals by end time, then counts overlaps.
     */
    static class Solution {
        // Original method: returns minimum removals for non-overlapping intervals
        public int eraseOverlapIntervals(int[][] a){Arrays.sort(a,Comparator.comparingInt(x->x[1]));int end=a[0][1],rm=0;
        for(int i=1;i<a.length;i++){if(a[i][0]<end)rm++;else end=a[i][1];}return rm;}
          // Original main: tests with sample intervals {{1,2},{2,3},{3,4},{1,3}}
        public static void main(String[] args) {
            System.out.println(new Solution().eraseOverlapIntervals(new int[][]{{1,2},{2,3},{3,4},{1,3}}));
        }
    }

    /**
     * Program entry point: delegates to Solution.main to run the demo.
     */
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[[1,2],[2,3],[3,4],[1,3]] → remove 1

Also asked: Amazon

Approach

Parallel min stack: push min(x, curMin) with each value.

Easy Algorithm

1. ops runner: MinStack commands return outputs

Code (Java)

import java.util.*;

/**
 * Main entry point for the MinStack demonstration.
 * Delegates to Solution.main to execute the example.
 */
public class Main {
    /**
     * Solution class containing the MinStack implementation and a runner
     * that processes a list of operations (commands) against it.
     */
    static class Solution {
        /**
         * MinStack implementation using two deques:
         * - st stores the pushed values
         * - mn stores the running minimum at each depth
         * All operations run in O(1) time.
         */
        static class MinStack{Deque<Integer> st=new ArrayDeque<>(), mn=new ArrayDeque<>(); // two stacks: values and running minima
        void push(int x){st.push(x);mn.push(mn.isEmpty()?x:Math.min(mn.peek(),x));} // push value and new min
        void pop(){st.pop();mn.pop();} int top(){return st.peek();} int getMin(){return mn.peek();}} // pop both; top returns last value; getMin returns current minimum
        /**
         * Executes a sequence of MinStack operations.
         * @param ops list of operations, each a list where first element is method name
         * @return list of results (null for void ops, value for top/getMin)
         */
        public List<Object> runMinStack(List<List<Object>> ops){MinStack s=null;List<Object> out=new ArrayList<>();
        for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("MinStack")){s=new MinStack();out.add(null);}
        else if(m.equals("push")){s.push(((Number)op.get(1)).intValue());out.add(null);}
        else if(m.equals("pop")){s.pop();out.add(null);} else if(m.equals("top"))out.add(s.top()); else out.add(s.getMin());}
        return out;}
          public static void main(String[] args) {
            System.out.println(new Solution().runMinStack(List.of(List.of("MinStack"),List.of("push",-2),List.of("push",0),List.of("push",-3),List.of("getMin"),List.of("pop"),List.of("top"),List.of("getMin"))));
          }
    }

    /**
     * Program entry point: calls Solution.main to run the built-in example.
     */
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

push -2,-3; getMin→-3

Also asked: Amazon, Bloomberg

Approach

Traverse 2n with decreasing stack of indices; fill when larger seen.

Easy Algorithm

1. ans fill -1; stack indices
2. for i in 0..2n-1: while stack top < nums[i%n] set ans

Code (Java)

// Import utility classes for collections and arrays
import java.util.*;

// Main class containing the solution and program entry point
public class Main {
    // Solution class containing the next greater element algorithm for circular arrays
    // Static nested class implementing the next greater element algorithm
    static class Solution {
        // Method to find next greater elements in circular array using monotonic stack
        public int[] nextGreaterElements(int[] a){int n=a.length;int[] ans=new int[n];Arrays.fill(ans,-1);Deque<Integer> st=new ArrayDeque<>();
        // Iterate twice over array to simulate circular behavior, maintain decreasing stack
        for(int i=0;i<2*n;i++){int x=a[i%n];while(!st.isEmpty()&&a[st.peek()]<x)ans[st.pop()]=x;if(i<n)st.push(i);}return ans;}
          // Main method in Solution class for demonstration
          public static void main(String[] args) {
            // Test with sample input [1,2,1] and print result
            System.out.println(Arrays.toString(new Solution().nextGreaterElements(new int[]{1,2,1})));
          }
    // End of Solution class
    }
    
    // Entry point: delegates to Solution.main to run the demo
    // Program entry point that delegates to Solution.main
    public static void main(String[] args) {
        // Call Solution's main method to run demo
        Solution.main(args);
    }
// End of Main class
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,2,1]→[2,-1,2]

Also asked: Amazon

Approach

Stack of survivors; resolve collisions when right-moving meets left-moving.

Easy Algorithm

1. for each a: while collision possible resolve
2. push if survives

Code (Java)

import java.util.*;

// Main entry point for the program
public class Main {
    // Solution class containing the asteroid collision algorithm
    static class Solution {
        // Asteroid collision method - resolves collisions between asteroids moving in opposite directions
        public int[] asteroidCollision(int[] a){Deque<Integer> st=new ArrayDeque<>();
        for(int x:a){boolean live=true;while(live&&!st.isEmpty()&&st.peek()>0&&x<0){int y=st.peek();if(y<-x)st.pop();else{if(y==-x)st.pop();live=false;}}
        if(live)st.push(x);}int[] ans=new int[st.size()];for(int i=ans.length-1;i>=0;i--)ans[i]=st.pop();return ans;}
        // Main method in Solution class for testing
        public static void main(String[] args) {
            System.out.println(Arrays.toString(new Solution().asteroidCollision(new int[]{5,10,-5})));
        }
    }
    // Main method that delegates to Solution.main
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[5,10,-5]→[5,10]

Also asked: Amazon, Lyft

Approach

BFS; for each level size, drain that many nodes.

Easy Algorithm

1. queue root
2. while queue: take level size, collect vals, enqueue children

Code (Java)

// Import Java utility classes like List, Queue, ArrayDeque, and ArrayList.
import java.util.*;

// Main entry class containing the Solution and a delegating main method.
public class Main {
    // Solution class containing the level order traversal algorithm and TreeNode definition
    // Static inner class Solution encapsulating the level-order traversal logic and tree utilities.
    static class Solution {
        // In guide: use TreeNode; HTML lab converts arrays.
        // levelOrder performs breadth-first traversal, returning a list of levels each as a list of node values.
        public List<List<Integer>> levelOrder(TreeNode root){List<List<Integer>> res=new ArrayList<>();if(root==null)return res;
        // Initialize a queue with the root node to start level-order processing.
        Queue<TreeNode> q=new ArrayDeque<>();q.add(root);
        // While queue has nodes, capture current level size, then iterate that many nodes to build the level list.
        while(!q.isEmpty()){int sz=q.size();List<Integer> lvl=new ArrayList<>();
        // For each node in the current level, record its value and enqueue its non-null children.
        for(int i=0;i<sz;i++){TreeNode n=q.poll();lvl.add(n.val);if(n.left!=null)q.add(n.left);if(n.right!=null)q.add(n.right);}res.add(lvl);}
        // Return the accumulated list of levels after the queue is exhausted.
        return res;}
        // TreeNode defines a binary tree node with an integer value and left/right child references.
        static class TreeNode{int val;TreeNode left,right;TreeNode(int v){val=v;}}

        // Helper to build a binary tree from a level-order array (with nulls for missing nodes)
        // arrToTree builds a binary tree from a level-order array where null represents missing nodes.
        static TreeNode arrToTree(Integer[] arr) {
            // Return null for empty or null input arrays, or when the first element is null.
            if (arr == null || arr.length == 0 || arr[0] == null) return null;
            // Create the root node from the first array element.
            TreeNode root = new TreeNode(arr[0]);
            // Queue used to attach children to nodes in level order.
            Queue<TreeNode> queue = new ArrayDeque<>();
            // Seed the queue with the root node.
            queue.add(root);
            // Index i tracks the next array element to consume as a child.
            int i = 1;
            // Process nodes until the queue is empty or all array elements are consumed.
            while (!queue.isEmpty() && i < arr.length) {
                // Dequeue the next parent node to attach its children.
                TreeNode current = queue.poll();
                // Left child
                // If a left child value exists, create the node, link it, and enqueue it.
                if (i < arr.length && arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.add(current.left);
                }
                // Advance index to the potential right child position.
                i++;
                // Right child
                // If a right child value exists, create the node, link it, and enqueue it.
                if (i < arr.length && arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.add(current.right);
                }
                // Advance index past the right child for the next loop iteration.
                i++;
            }
            // Return the fully constructed tree root.
            return root;
        }

          // Solution's main demonstrates levelOrder on a sample tree [3,9,20,null,null,15,7].
          public static void main(String[] args) {
            // Build the tree from the array and print the level-order traversal result.
            System.out.println(new Solution().levelOrder(arrToTree(new Integer[]{3,9,20,null,null,15,7}))); /* assume helpers */
          }
    }

    // Outer Main.main delegates to Solution.main for execution.
    public static void main(String[] args) {
        // Invoke the demonstration in Solution.
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

Also asked: Amazon, Meta

Approach

DFS with (low, high) open bounds on allowed values.

Easy Algorithm

1. dfs(node,lo,hi)
2. val must be in (lo,hi); recurse children

Code (Java)

import java.util.*;
// Original import from snippet
public class Main {
    // Snippet's Solution class made static nested
    static class Solution {
        // Validates BST using DFS with open bounds (lo, hi)
        public boolean isValidBST(TreeNode root){return dfs(root,Long.MIN_VALUE,Long.MAX_VALUE);}
        // Recursive DFS: node value must be strictly between lo and hi
        boolean dfs(TreeNode n,long lo,long hi){if(n==null)return true;if(n.val<=lo||n.val>=hi)return false;return dfs(n.left,lo,n.val)&&dfs(n.right,n.val,hi);}
        // TreeNode definition from snippet
        static class TreeNode{int val;TreeNode left,right;TreeNode(int v){val=v;}}
        // Snippet's main: tests with null tree (should print true)
        public static void main(String[] args) {
            System.out.println(new Solution().isValidBST(/*tree*/null));
        }
    }
    // Main entry point: delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args); // the snippet's own demo: an empty tree is a valid BST
        Solution sol = new Solution();
        // Valid BST:    2          (1 < 2 < 3)
        //              / \
        //             1   3
        Solution.TreeNode ok = new Solution.TreeNode(2);
        ok.left = new Solution.TreeNode(1);
        ok.right = new Solution.TreeNode(3);
        System.out.println(sol.isValidBST(ok)); // true
        // Invalid: 4 is in the right subtree of 5 but is smaller than 5 (3 breaks the same bound)
        //       5
        //      / \
        //     1   4
        //        / \
        //       3   6
        Solution.TreeNode bad = new Solution.TreeNode(5);
        bad.left = new Solution.TreeNode(1);
        bad.right = new Solution.TreeNode(4);
        bad.right.left = new Solution.TreeNode(3);
        bad.right.right = new Solution.TreeNode(6);
        System.out.println(sol.isValidBST(bad)); // false
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,1,3] true; [5,1,4,null,null,3,6] false

Also asked: Amazon, Meta

Approach

For each node, diameter through node = leftH+rightH; track global max.

Easy Algorithm

1. dfs returns height
2. update best = max(best, L+R)

Code (Java)

import java.util.*; // import all utilities

// Main class to run the program
public class Main {
    // Solution class containing binary tree diameter algorithm
    static class Solution {
        // Field to track maximum diameter
        int best=0;public int diameterOfBinaryTree(TreeNode root){best=0;height(root);return best;} // computes diameter of binary tree
        // Helper method to compute height and update best diameter
        int height(TreeNode n){if(n==null)return 0;int L=height(n.left),R=height(n.right);best=Math.max(best,L+R);return 1+Math.max(L,R);} // returns height of node
        // TreeNode definition for binary tree nodes
        static class TreeNode{int val;TreeNode left,right;TreeNode(int v){val=v;}} // simple binary tree node
        // Main method in Solution for testing with null tree
        public static void main(String[] args) {
            System.out.println(new Solution().diameterOfBinaryTree(null));
        }
    }
    // Main entry point
    public static void main(String[] args) {
        Solution.main(args); // the snippet's own demo: an empty tree has diameter 0
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        Solution.TreeNode root = new Solution.TreeNode(1);
        root.left = new Solution.TreeNode(2);
        root.right = new Solution.TreeNode(3);
        root.left.left = new Solution.TreeNode(4);
        root.left.right = new Solution.TreeNode(5);
        // Longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3): 3 edges
        System.out.println(new Solution().diameterOfBinaryTree(root)); // 3
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,2,3,4,5] → 3

Also asked: Amazon

Approach

DFS accumulate path; when leaf and sum matches, copy path.

Easy Algorithm

1. dfs(node,remain,path)
2. leaf & remain==val → record

Code (Java)

import java.util.*;

// Main class for JDoodle online compiler
public class Main {
    // Solution class for Path Sum II problem - finds all root-to-leaf paths summing to targetSum
    static class Solution {
    // Returns all root-to-leaf paths where path sum equals target t
    public List<List<Integer>> pathSum(TreeNode root,int t){List<List<Integer>> res=new ArrayList<>();dfs(root,t,new ArrayList<>(),res);return res;}
    // DFS helper: accumulates path, checks leaf with remaining sum, backtracks
    void dfs(TreeNode n,int rem,List<Integer> path,List<List<Integer>> res){if(n==null)return;path.add(n.val);
    if(n.left==null&&n.right==null&&rem==n.val)res.add(new ArrayList<>(path));
    else{dfs(n.left,rem-n.val,path,res);dfs(n.right,rem-n.val,path,res);}path.remove(path.size()-1);}
    // Binary tree node definition
    static class TreeNode{int val;TreeNode left,right;TreeNode(int v){val=v;}}
      // Demonstrates pathSum with null tree (returns empty list)
      public static void main(String[] args) {
        System.out.println(new Solution().pathSum(null,22));
      }
    }
    // Program entry point delegates to Solution.main for demo
    public static void main(String[] args) {
        Solution.main(args); // the snippet's own demo: an empty tree has no paths
        //          5
        //         / \
        //        4   8
        //       /   / \
        //     11  13   4
        //    /  \     / \
        //   7    2   5   1
        Solution.TreeNode root = new Solution.TreeNode(5);
        root.left = new Solution.TreeNode(4);
        root.right = new Solution.TreeNode(8);
        root.left.left = new Solution.TreeNode(11);
        root.left.left.left = new Solution.TreeNode(7);
        root.left.left.right = new Solution.TreeNode(2);
        root.right.left = new Solution.TreeNode(13);
        root.right.right = new Solution.TreeNode(4);
        root.right.right.left = new Solution.TreeNode(5);
        root.right.right.right = new Solution.TreeNode(1);
        // Two root-to-leaf paths sum to 22: 5+4+11+2 and 5+8+4+5
        System.out.println(new Solution().pathSum(root, 22)); // [[5, 4, 11, 2], [5, 8, 4, 5]]
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

classic tree target 22 → two paths

Also asked: Amazon

Approach

Reverse preorder: process right, left, then splice node to prev.

Easy Algorithm

1. dfs(node): flatten right then left; node.right=prev; node.left=null; prev=node

Code (Java)

import java.util.*;
public class Main {
    // Solution class containing the tree flattening algorithm
    static class Solution {
TreeNode prev=null;public void flatten(TreeNode root){if(root==null)return;flatten(root.right);flatten(root.left);root.right=prev;root.left=null;prev=root;}
public TreeNode flattenTree(TreeNode root){prev=null;flatten(root);return root;}
static class TreeNode{int val;TreeNode left,right;TreeNode(int v){val=v;}}
  public static void main(String[] args) {
    /* flatten then serialize right chain */
  }
}
    // Main entry point: runs the original main and demonstrates the algorithm
    public static void main(String[] args) {
        // Call the original main (currently empty)
        Solution.main(args);
        // Build the sample tree: 1,2,5,3,4,null,6
        //       1
        //      / \
        //     2   5
        //    / \   \
        //   3   4   6
        Solution.TreeNode root = new Solution.TreeNode(1);
        root.left = new Solution.TreeNode(2);
        root.right = new Solution.TreeNode(5);
        root.left.left = new Solution.TreeNode(3);
        root.left.right = new Solution.TreeNode(4);
        root.right.right = new Solution.TreeNode(6);
        // Flatten the tree to a right-linked list (preorder)
        Solution sol = new Solution();
        sol.flattenTree(root);
        // Print the right-spine values
        System.out.print("Flattened right spine: ");
        Solution.TreeNode curr = root;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        }
        System.out.println();
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,2,5,3,4,null,6] → [1,null,2,null,3,null,4,null,5,null,6]

Also asked: Amazon, Microsoft

Approach

Build graph+indegree; BFS zero-indegree; if count<n cycle.

Easy Algorithm

1. Kahn BFS
2. if taken<n return [] else order

Code (Java)

import java.util.*;

// Main class to run the course schedule solution
public class Main {
    // Solution class implementing Kahn's topological sort algorithm for course scheduling
    static class Solution {
        // Method to find a valid course order given prerequisites, returns empty array if cycle detected
        public int[] findOrder(int n,int[][] pre){List<List<Integer>> g=new ArrayList<>();int[] indeg=new int[n]; // Create adjacency list and indegree array
for(int i=0;i<n;i++)g.add(new ArrayList<>());for(int[] e:pre){g.get(e[1]).add(e[0]);indeg[e[0]]++;} // Initialize graph and build edges with indegree counts
Queue<Integer> q=new ArrayDeque<>();for(int i=0;i<n;i++)if(indeg[i]==0)q.add(i); // Queue courses with zero prerequisites
int[] ord=new int[n];int k=0;while(!q.isEmpty()){int u=q.poll();ord[k++]=u;for(int v:g.get(u))if(--indeg[v]==0)q.add(v);} // Process courses in topological order
return k==n?ord:new int[0];} // Return order if all courses taken, else empty array
        // Main method to test the findOrder function with sample input
        public static void main(String[] args) {
            System.out.println(Arrays.toString(new Solution().findOrder(2,new int[][]{{1,0}}))); // Test case: 2 courses, 1 requires 0
        }
    }

    // Entry point that delegates to Solution's main method
    public static void main(String[] args) {
        Solution.main(args); // Call Solution's main to execute the test
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

2 courses [[1,0]] → [0,1]

Also asked: Amazon, Uber

Approach

Dijkstra on adjacency list; answer = max finite dist.

Easy Algorithm

1. build graph
2. Dijkstra from k
3. max dist or -1

Code (Java)

import java.util.*;
public class Main {
    // Solution class implementing Dijkstra's algorithm for network delay time
    static class Solution {
        // Original method: computes minimum time for signal to reach all nodes from k
        public int networkDelayTime(int[][] times,int n,int k){List<int[]>[] g=new List[n+1];for(int i=1;i<=n;i++)g[i]=new ArrayList<>();
        for(int[] e:times)g[e[0]].add(new int[]{e[1],e[2]});int[] dist=new int[n+1];Arrays.fill(dist,Integer.MAX_VALUE);dist[k]=0;
        PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));pq.add(new int[]{0,k});
        while(!pq.isEmpty()){int[] cur=pq.poll();int d=cur[0],u=cur[1];if(d>dist[u])continue;for(int[] e:g[u]){int v=e[0],w=e[1];if(d+w<dist[v]){dist[v]=d+w;pq.add(new int[]{dist[v],v});}}}
        int ans=0;for(int i=1;i<=n;i++){if(dist[i]==Integer.MAX_VALUE)return -1;ans=Math.max(ans,dist[i]);}return ans;}
        // Original main method that tests the solution with sample input
          public static void main(String[] args) {
            System.out.println(new Solution().networkDelayTime(new int[][]{{2,1,1},{2,3,1},{3,4,1}},4,2));
          }
    }
    // Entry point that delegates to Solution.main
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

n=4 times=[[2,1,1],[2,3,1],[3,4,1]] k=2 → 2

Also asked: Amazon, Uber

Approach

DFS inland from ocean borders; intersection of reachable sets.

Easy Algorithm

1. mark pacific-reachable from top/left
2. atlantic from bottom/right
3. intersect

Code (Java)

import java.util.*;

// Main class to run the Pacific Atlantic Water Flow solution
public class Main {
    // Solution class containing the algorithm to find cells that can flow to both oceans
    static class Solution {
        // Finds all coordinates from which water can flow to both Pacific and Atlantic oceans
        public List<List<Integer>> pacificAtlantic(int[][] h){int R=h.length,C=h[0].length;boolean[][] P=new boolean[R][C],A=new boolean[R][C];
        // Start DFS from Pacific borders (top and left)
        for(int r=0;r<R;r++){dfs(h,P,r,0,0);dfs(h,A,r,C-1,0);}for(int c=0;c<C;c++){dfs(h,P,0,c,0);dfs(h,A,R-1,c,0);}
        // Collect cells reachable from both oceans
        List<List<Integer>> res=new ArrayList<>();for(int r=0;r<R;r++)for(int c=0;c<C;c++)if(P[r][c]&&A[r][c])res.add(List.of(r,c));return res;}
        // Depth-first search to mark reachable cells flowing uphill from ocean edges
        void dfs(int[][] h,boolean[][] seen,int r,int c,int prev){if(r<0||c<0||r>=h.length||c>=h[0].length||seen[r][c]||h[r][c]<prev)return;
        seen[r][c]=true;dfs(h,seen,r+1,c,h[r][c]);dfs(h,seen,r-1,c,h[r][c]);dfs(h,seen,r,c+1,h[r][c]);dfs(h,seen,r,c-1,h[r][c]);}
        // Demo main method that runs the algorithm on a sample height matrix
          public static void main(String[] args) {
            System.out.println(new Solution().pacificAtlantic(new int[][]{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}}));
          }
    }
    // Entry point: delegates to Solution's main method
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

classic 5x5 heights → 7 cells

Also asked: Amazon, Google

Approach

Union-Find; start with n components; decrement on successful union.

Easy Algorithm

1. UF init n
2. union each edge
3. return components

Code (Java)

import java.util.*;
// Main class containing the Solution implementation for counting connected components
public class Main {
    // Solution class implementing Union-Find to count connected components in an undirected graph
    static class Solution {
        // countComponents method: returns number of connected components using Union-Find with path compression
        public int countComponents(int n,int[][] edges){int[] p=new int[n];for(int i=0;i<n;i++)p[i]=i;int comp=n; // initialize parent array and component count
        java.util.function.IntUnaryOperator find=new java.util.function.IntUnaryOperator(){public int applyAsInt(int x){return p[x]==x?x:(p[x]=applyAsInt(p[x]));}}; // find with path compression
        for(int[] e:edges){int a=find.applyAsInt(e[0]),b=find.applyAsInt(e[1]);if(a!=b){p[b]=a;comp--;}}return comp;} // union edges and count components
        // Main method in Solution class for demonstration
          public static void main(String[] args) {
            System.out.println(new Solution().countComponents(5,new int[][]{{0,1},{1,2},{3,4}})); // test with 5 nodes and 3 edges
          }
    }
    // Main entry point that delegates to Solution.main
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

n=5 edges=[[0,1],[1,2],[3,4]] → 2

Also asked: Amazon

Approach

Build inequality edges from adjacent words; Kahn with min-heap for lex-smallest.

Easy Algorithm

1. compare adjacent words for first diff edge
2. detect prefix invalid
3. topo with PQ

Code (Java)

import java.util.*;

public class Main {
    // Solution class for Alien Dictionary problem
    // Derives lexicographically smallest valid character order from sorted dictionary words
    static class Solution {
    public String alienOrder(String[] words){Map<Character,Set<Character>> g=new HashMap<>();int[] indeg=new int[26];boolean[] seen=new boolean[26]; // Build graph, indegree, and track seen chars
    for(String w:words)for(char c:w.toCharArray())seen[c-'a']=true; // Mark all characters that appear
    for(int i=0;i+1<words.length;i++){String a=words[i],b=words[i+1];if(a.length()>b.length()&&a.startsWith(b))return ""; // Invalid prefix case
    int len=Math.min(a.length(),b.length());for(int j=0;j<len;j++)if(a.charAt(j)!=b.charAt(j)){ // Find first differing char
    char u=a.charAt(j),v=b.charAt(j);g.computeIfAbsent(u,k->new HashSet<>());if(g.get(u).add(v))indeg[v-'a']++;break;}} // Add edge u->v if new
    PriorityQueue<Character> q=new PriorityQueue<>();for(char c='a';c<='z';c++)if(seen[c-'a']&&indeg[c-'a']==0)q.add(c); // Min-heap for lexicographically smallest topo order
    StringBuilder sb=new StringBuilder();int need=0;for(boolean s:seen)if(s)need++; // Count unique chars needed
    while(!q.isEmpty()){char u=q.poll();sb.append(u);for(char v:g.getOrDefault(u,Set.of()))if(--indeg[v-'a']==0)q.add(v);} // Kahn's algorithm with PQ
    return sb.length()==need?sb.toString():"";} // Return order if all chars processed, else cycle detected
      public static void main(String[] args) {
        System.out.println(new Solution().alienOrder(new String[]{"wrt","wrf","er","ett","rftt"})); // Expected: "wertf"
      }
    }
    // Main entry point delegates to Solution.main
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

["wrt","wrf","er","ett","rftt"] → "wertf"

Also asked: Amazon, Airbnb

Approach

(maxFreq-1)*(n+1) + count of tasks with maxFreq, then max with tasks.length.

Easy Algorithm

1. count freqs
2. maxf and cnt at maxf
3. max(len, (maxf-1)*(n+1)+cnt)

Code (Java)

import java.util.*;
// Main class to run the Task Scheduler solution
public class Main {

    // Solution class implementing the Task Scheduler algorithm
    // Uses greedy formula: max(tasks.length, (maxFreq-1)*(n+1) + countOfMaxFreq)
    static class Solution {
public int leastInterval(char[] tasks,int n){int[] f=new int[26];for(char c:tasks)f[c-'A']++;
int maxf=0,cnt=0;for(int x:f){if(x>maxf){maxf=x;cnt=1;}else if(x==maxf)cnt++;}
return Math.max(tasks.length,(maxf-1)*(n+1)+cnt);}
  public static void main(String[] args) {
    System.out.println(new Solution().leastInterval(new char[]{'A','A','A','B','B','B'},2));
  }
    }

    // Entry point: delegates to Solution.main for demonstration
    public static void main(String[] args) {
        Solution.main(args);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

AAABBB n=2 → 8

Also asked: Amazon

Approach

Max-heap lows + min-heap highs; rebalance sizes.

Easy Algorithm

1. ops MedianFinder

Code (Java)

import java.util.*;
public class Main {
// MedianFinder solution using two heaps: a max-heap (lo) for the lower half and a min-heap (hi) for the upper half
static class Solution {
// Inner class MF maintains two priority queues to find median in O(log n) per insertion
static class MF{PriorityQueue<Integer> lo=new PriorityQueue<>(Collections.reverseOrder()),hi=new PriorityQueue<>(); // lo = max-heap (lower half), hi = min-heap (upper half)
void addNum(int x){lo.add(x);hi.add(lo.poll());if(hi.size()>lo.size())lo.add(hi.poll());} // push to lo, move max to hi, rebalance if hi larger
double findMedian(){return lo.size()>hi.size()?lo.peek():(lo.peek()+hi.peek())/2.0;} // median is top of lo if odd, average of tops if even
}
// Executes a sequence of operations: ["MedianFinder"], ["addNum", val], ["findMedian"] and returns list of results (null for void ops)
public List<Object> runMedianFinder(List<List<Object>> ops){MF m=null;List<Object> out=new ArrayList<>();
for(List<Object> op:ops){String k=(String)op.get(0);if(k.equals("MedianFinder")){m=new MF();out.add(null);}
else if(k.equals("addNum")){m.addNum(((Number)op.get(1)).intValue());out.add(null);} else out.add(m.findMedian());}
return out;}
  public static void main(String[] args) {
    System.out.println(new Solution().runMedianFinder(List.of(/*ops*/)));
  }
}
public static void main(String[] args) {
    Solution.main(args); // the snippet's own demo: an empty list of operations gives []
    // Stream 1, 2 then 3: the median is 1.5 after two numbers and 2.0 after three
    List<List<Object>> ops = List.of(List.of("MedianFinder"), List.of("addNum", 1), List.of("addNum", 2),
            List.of("findMedian"), List.of("addNum", 3), List.of("findMedian"));
    System.out.println(new Solution().runMedianFinder(ops)); // [null, null, null, 1.5, null, 2.0]
}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

add 1,2 → median 1.5; add 3 → 2

Also asked: Amazon, Google

Approach

Track max and min products ending here (sign flips).

Easy Algorithm

1. imax=imin=best=a[0]
2. for x: candidates x,imax*x,imin*x; update

Code (Java)

// Imports Java utility classes like List, Map, etc.
import java.util.*;
// Defines the outer Main class that holds the Solution inner class and a bootstrap main method.
public class Main {
// Declares a static inner class Solution containing the maxProduct algorithm and a demo main.
static class Solution {
// Defines maxProduct method that computes maximum product subarray using dynamic programming with imax/imin tracking.
public int maxProduct(int[] a){int imax=a[0],imin=a[0],best=a[0];
// Iterates through array updating imax (max product ending here), imin (min product ending here), and best overall max.
for(int i=1;i<a.length;i++){int x=a[i];int c1=imax*x,c2=imin*x;imax=Math.max(x,Math.max(c1,c2));imin=Math.min(x,Math.min(c1,c2));best=Math.max(best,imax);}return best;}
  // Solution's main method serves as a demo entry point for testing maxProduct.
  public static void main(String[] args) {
    // Runs maxProduct on sample input [2,3,-2,4] and prints the result (expected 6).
    System.out.println(new Solution().maxProduct(new int[]{2,3,-2,4}));
  }
}
// Outer Main's main method delegates to Solution.main to execute the demo.
public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,3,-2,4]→6

Also asked: Amazon

Approach

Left-to-right enforce left neighbor; right-to-left enforce right; take max.

Easy Algorithm

1. candies=1s
2. LTR then RTL peaks
3. sum

Code (Java)

// Import Java utility classes for array operations
import java.util.*;
// Define the outer Main class that holds the solution and entry point
public class Main {
    /* Solution class implementing two-pass greedy candy distribution */
    // Static nested class containing the candy distribution algorithm
    static class Solution {
// candy method: initialize each child with 1 candy, then prepare for two passes
public int candy(int[] r){int n=r.length;int[] c=new int[n];Arrays.fill(c,1);
// Left-to-right pass: if current rating > left neighbor, give one more candy than left
for(int i=1;i<n;i++)if(r[i]>r[i-1])c[i]=c[i-1]+1;
// Right-to-left pass: if current rating > right neighbor, ensure at least right+1 candies
for(int i=n-2;i>=0;i--)if(r[i]>r[i+1])c[i]=Math.max(c[i],c[i+1]+1);
// Sum all candies and return the minimum total required
int s=0;for(int x:c)s+=x;return s;}
  // Solution's main method for quick demonstration
  public static void main(String[] args) {
    // Test with ratings [1,0,2] expecting 5 candies (1+2+2)
    System.out.println(new Solution().candy(new int[]{1,0,2}));
  }
    }
    /* Entry point that delegates to Solution's main for demonstration */
    // Main class entry point delegates to Solution.main for execution
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,0,2]→5

Also asked: Amazon

Approach

If total gas<total cost impossible; else start after the worst deficit prefix.

Easy Algorithm

1. track tank and total
2. when tank<0 reset start=i+1 tank=0

Code (Java)

import java.util.*;
public class Main {
  /** Main class to run the example. */
  static class Solution {
    /** Solution class containing the canCompleteCircuit method. */
    /** Returns the starting gas station index if circuit possible, else -1. */
    public int canCompleteCircuit(int[] gas,int[] cost){int tank=0,total=0,start=0;
    for(int i=0;i<gas.length;i++){int d=gas[i]-cost[i];tank+=d;total+=d;if(tank<0){start=i+1;tank=0;}}return total<0?-1:start;}
    /** Main method for testing the solution. */
    public static void main(String[] args) {
      System.out.println(new Solution().canCompleteCircuit(new int[]{1,2,3,4,5},new int[]{3,4,5,1,2}));
    }
  }
  /** Entry point that invokes Solution's main. */
  public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

gas=[1,2,3,4,5] cost=[3,4,5,1,2] → 3

Also asked: Amazon, Uber

Approach

Track farthest reachable; if i>farthest fail; update farthest.

Easy Algorithm

1. far=0
2. for i: if i>far false; far=max(far,i+a[i])

Code (Java)

import java.util.*;
public class Main {
    // Solution class containing the Jump Game greedy algorithm
    static class Solution {
        // Greedy approach: track farthest reachable index
        public boolean canJump(int[] a){int far=0;for(int i=0;i<a.length;i++){if(i>far)return false;far=Math.max(far,i+a[i]);}return true;}
          public static void main(String[] args) {
            System.out.println(new Solution().canJump(new int[]{2,3,1,1,4}));
          }
        }
    // Entry point delegates to Solution.main
    public static void main(String[] args){ Solution.main(args); }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[2,3,1,1,4] true; [3,2,1,0,4] false

Also asked: Amazon, Uber

Approach

If total odd false; DP whether subset sum total/2 achievable.

Easy Algorithm

1. target=sum/2
2. boolean dp; update backward

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test case from the snippet: [1,5,11,5] -> true (1+5+5 = 11)
        System.out.println(sol.canPartition(new int[]{1,5,11,5})); // true
        // Additional test: odd total sum -> false
        System.out.println(sol.canPartition(new int[]{1,2,3,5})); // false
        // Additional test: [3,3,3,4,5] sum=18 target=9 -> true (4+5=9)
        System.out.println(sol.canPartition(new int[]{3,3,3,4,5})); // true
    }
}

class Solution {
public boolean canPartition(int[] a){int s=0;for(int x:a)s+=x;if((s&1)==1)return false;int t=s/2;boolean[] dp=new boolean[t+1];dp[0]=true;
for(int x:a)for(int j=t;j>=x;j--)dp[j]|=dp[j-x];return dp[t];}
  public static void main(String[] args) {
    System.out.println(new Solution().canPartition(new int[]{1,5,11,5}));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[1,5,11,5] true

Also asked: Amazon

Approach

dp[i][j]=diag+1 if equal else max(left,up).

Easy Algorithm

1. (m+1)x(n+1) table
2. fill; return dp[m][n]

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Create Solution instance and test with sample data
        Solution solution = new Solution();
        int result = solution.longestCommonSubsequence("abcde", "ace");
        System.out.println("LCS length of 'abcde' and 'ace': " + result);
        // Expected: 3 ("ace")

        // Additional test cases
        System.out.println("LCS length of 'abc' and 'abc': " + solution.longestCommonSubsequence("abc", "abc")); // 3
        System.out.println("LCS length of 'abc' and 'def': " + solution.longestCommonSubsequence("abc", "def")); // 0
        System.out.println("LCS length of 'bsbininm' and 'jmjkbkjkv': " + solution.longestCommonSubsequence("bsbininm", "jmjkbkjkv")); // 1
    }
}

// Solution class kept exactly as provided in the snippet
class Solution {
public int longestCommonSubsequence(String a,String b){int m=a.length(),n=b.length();int[][] dp=new int[m+1][n+1];
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=a.charAt(i-1)==b.charAt(j-1)?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]);
return dp[m][n];}
  public static void main(String[] args) {
    System.out.println(new Solution().longestCommonSubsequence("abcde","ace"));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

abcde / ace → 3

Also asked: Amazon, Google

Approach

Stacks for counts and partial strings; on ']' expand.

Easy Algorithm

1. scan; digit→count; '[' push; ']' pop & repeat

Code (Java)

import java.util.*;

public class Main {
    /**
     * Main entry point to demonstrate the Solution.decodeString method.
     */
    public static void main(String[] args) {
        Solution solution = new Solution();
        // Test case from the snippet
        System.out.println("Test 1: " + solution.decodeString("3[a]2[bc]")); // expected "aaabcbc"
        // Additional test cases
        System.out.println("Test 2: " + solution.decodeString("3[a2[c]]")); // expected "accaccacc"
        System.out.println("Test 3: " + solution.decodeString("2[abc]3[cd]ef")); // expected "abcabccdcdcdef"
    }
}

/**
 * Solution class implementing the decodeString algorithm using two stacks.
 * This class is kept exactly as provided in the snippet.
 */
class Solution {
    public String decodeString(String s){Deque<Integer> cnt=new ArrayDeque<>();Deque<StringBuilder> str=new ArrayDeque<>();
    StringBuilder cur=new StringBuilder();int n=0;
    for(char c:s.toCharArray()){if(Character.isDigit(c))n=n*10+c-'0';
    else if(c=='['){cnt.push(n);str.push(cur);cur=new StringBuilder();n=0;}
    else if(c==']'){StringBuilder prev=str.pop();int k=cnt.pop();for(int i=0;i<k;i++)prev.append(cur);cur=prev;}
    else cur.append(c);}return cur.toString();}
      public static void main(String[] args) {
        System.out.println(new Solution().decodeString("3[a]2[bc]"));
      }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

"3[a]2[bc]" → aaabcbc

Also asked: Amazon, Google

Approach

Parse numbers; apply * / immediately to last term; + - push signed terms.

Easy Algorithm

1. last sign; on op flush number
2. sum stack at end

Code (Java)

import java.util.*; // Import Java utilities

// Main class to run sample calculations using the Solution class
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution(); // Create Solution instance
        System.out.println("Test 1: 3+2*2 = " + sol.calculate("3+2*2")); // Expected 7
        System.out.println("Test 2: 3/2 = " + sol.calculate("3/2"));     // Expected 1
        System.out.println("Test 3: 3+5/2 = " + sol.calculate("3+5/2")); // Expected 5
        System.out.println("Test 4: 1+2*3-4/2 = " + sol.calculate("1+2*3-4/2")); // Expected 5
    }
}

// Solution class implementing basic calculator II (handles + - * / without parentheses)
class Solution {
public int calculate(String s){Deque<Integer> st=new ArrayDeque<>();char sign='+';int num=0;s=s.replace(" ",""); // Initialize stack, sign, number, remove spaces
for(int i=0;i<s.length();i++){char c=s.charAt(i);if(Character.isDigit(c))num=num*10+c-'0'; // Loop through characters, build number
if(!Character.isDigit(c)||i==s.length()-1){if(sign=='+')st.push(num);else if(sign=='-')st.push(-num); // Process previous sign when operator or end
else if(sign=='*')st.push(st.pop()*num);else st.push(st.pop()/num);sign=c;num=0;}} // Handle * / immediately, update sign, reset number
int sum=0;for(int x:st)sum+=x;return sum;} // Sum stack for final result
  public static void main(String[] args) { // Original test main
    System.out.println(new Solution().calculate("3+2*2")); // Print result for 3+2*2
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

"3+2*2" → 7

Also asked: Amazon, Meta

Approach

Split on /; push names; pop on '..'; ignore '.' and empties.

Easy Algorithm

1. stack parts
2. join with /; root if empty

Code (Java)

// Import Java utility classes for collections like Deque and ArrayDeque.
import java.util.*;

// Main class containing the demonstration of path simplification.
public class Main {
    // Main method entry point for running demo test cases.
    public static void main(String[] args) {
        // Demo: simplify a Unix absolute path
        // Create an instance of Solution to use its simplifyPath method.
        Solution solution = new Solution();
        // Define first test path with current directory, parent directory references.
        String path1 = "/a/./b/../../c/";
        // Print the input path for visibility.
        System.out.println("Input: " + path1);
        // Print the simplified path output from Solution.
        System.out.println("Output: " + solution.simplifyPath(path1));
        
        // Additional test cases
        // Define a simple absolute path with trailing slash.
        String path2 = "/home/";
        // Print input path.
        System.out.println("Input: " + path2);
        // Print simplified output.
        System.out.println("Output: " + solution.simplifyPath(path2));
        
        // Define path that attempts to go above root directory.
        String path3 = "/../";
        // Print input path.
        System.out.println("Input: " + path3);
        // Print simplified output (should remain root).
        System.out.println("Output: " + solution.simplifyPath(path3));
        
        // Define path with multiple consecutive slashes.
        String path4 = "/home//foo/";
        // Print input path.
        System.out.println("Input: " + path4);
        // Print simplified output (extra slashes removed).
        System.out.println("Output: " + solution.simplifyPath(path4));
    }
}

// Original Solution class from the snippet (must appear exactly as written)
// Solution class providing Unix path simplification logic.
class Solution {
// Method simplifyPath takes a Unix absolute path and returns canonical path using a stack.
public String simplifyPath(String path){Deque<String> st=new ArrayDeque<>();
// Split path by '/', process each component: skip empty or '.', handle '..' by popping stack, else push directory.
for(String p:path.split("/")){if(p.equals("")||p.equals("."))continue;if(p.equals("..")){if(!st.isEmpty())st.pollLast();}else st.addLast(p);}
// Join stack with '/' and prepend root '/' to form canonical path.
return "/"+String.join("/",st);}
  // Main method in Solution for quick standalone test (not used in demo).
  public static void main(String[] args) {
    // Run a sample simplification and print result.
    System.out.println(new Solution().simplifyPath("/a/./b/../../c/"));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

"/a/./b/../../c/" → "/c"

Also asked: Amazon, Meta

Approach

26-way children map; end flag on nodes.

Easy Algorithm

1. ops Trie

Code (Java)

import java.util.*;
class Solution {
static class Trie{static class N{N[] ch=new N[26];boolean end;} N root=new N();
void insert(String w){N n=root;for(char c:w.toCharArray()){int i=c-'a';if(n.ch[i]==null)n.ch[i]=new N();n=n.ch[i];}n.end=true;}
boolean search(String w){N n=find(w);return n!=null&&n.end;} boolean startsWith(String p){return find(p)!=null;}
N find(String w){N n=root;for(char c:w.toCharArray()){int i=c-'a';if(n.ch[i]==null)return null;n=n.ch[i];}return n;}}
public List<Object> runTrie(List<List<Object>> ops){Trie t=null;List<Object> out=new ArrayList<>();
for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("Trie")){t=new Trie();out.add(null);}
else if(m.equals("insert")){t.insert((String)op.get(1));out.add(null);}
else if(m.equals("search"))out.add(t.search((String)op.get(1))); else out.add(t.startsWith((String)op.get(1)));}
return out;}
  public static void main(String[] args) {
    System.out.println(new Solution().runTrie(/*ops*/));
  }
}

Design sketch. This outline shows structure only and is not meant to run as a single file, so it has no Run button. Use Copy to keep it as a starting point.

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

insert apple; search apple true; search app false; startsWith app true

Also asked: Amazon, Google

Approach

dp[i]=true if prefix s[0..i) breakable; try dict words ending at i.

Easy Algorithm

1. dp[0]=true
2. for i: if some j with dp[j] and s[j..i) in dict

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wordBreak("leetcode", List.of("leet", "code")));
        System.out.println(sol.wordBreak("applepenapple", List.of("apple", "pen")));
        System.out.println(sol.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat")));
    }
}

class Solution {
public boolean wordBreak(String s,List<String> wordDict){Set<String> set=new HashSet<>(wordDict);boolean[] dp=new boolean[s.length()+1];dp[0]=true; // DP array, dp[0]=true means empty string is breakable
for(int i=1;i<=s.length();i++)for(int j=0;j<i;j++)if(dp[j]&&set.contains(s.substring(j,i))){dp[i]=true;break;}return dp[s.length()];} // Check all prefixes ending at i
  public static void main(String[] args) { // Snippet's own main method
    System.out.println(new Solution().wordBreak("leetcode", List.of("leet","code"))); // Prints true
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

leetcode / ["leet","code"] true

Also asked: Amazon, Google

Approach

DFS from border O mark '#'; flip remaining O→X then '#'→O. Return board.

Easy Algorithm

1. mark border-connected O
2. flip
3. restore marks

Code (Java)

import java.util.*;

/**
 * Main entry point demonstrating the Surrounded Regions solution.
 * Creates a sample board, runs the capture algorithm, and prints the result.
 */
public class Main {
    public static void main(String[] args) {
        // Sample board: X = wall, O = region to potentially capture
        char[][] board = {
            {'X','X','X','X'},
            {'X','O','O','X'},
            {'X','X','O','X'},
            {'X','O','X','X'}
        };
        System.out.println("Original board:");
        printBoard(board);
        
        Solution solver = new Solution();
        char[][] result = solver.solve(board);
        
        System.out.println("\nBoard after capturing surrounded regions:");
        printBoard(result);
    }
    
    /** Helper to pretty-print a 2D char array. */
    private static void printBoard(char[][] b) {
        for (char[] row : b) {
            System.out.println(Arrays.toString(row));
        }
    }
}

/**
 * LeetCode 130 - Surrounded Regions.
 * Captures all 'O' regions surrounded by 'X' by flipping them to 'X'.
 * Regions connected to the border remain 'O'.
 * Uses DFS from border 'O's to mark them safe ('#'), then flips the rest.
 */
class Solution {
public char[][] solve(char[][] b){int R=b.length,C=b[0].length; // R=rows, C=cols
for(int r=0;r<R;r++){dfs(b,r,0);dfs(b,r,C-1);}for(int c=0;c<C;c++){dfs(b,0,c);dfs(b,R-1,c);} // DFS from all four borders
for(int r=0;r<R;r++)for(int c=0;c<C;c++){if(b[r][c]=='O')b[r][c]='X';else if(b[r][c]=='#')b[r][c]='O';}return b;} // Flip unmarked O->X, restore #->O
void dfs(char[][] b,int r,int c){if(r<0||c<0||r>=b.length||c>=b[0].length||b[r][c]!='O')return;b[r][c]='#'; // Bounds check & skip non-O; mark safe
dfs(b,r+1,c);dfs(b,r-1,c);dfs(b,r,c+1);dfs(b,r,c-1);} // Recurse 4 directions
  public static void main(String[] args) { // Original test harness
    System.out.println(Arrays.deepToString(new Solution().solve(new char[][]{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}})));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

classic board capture

Also asked: Amazon, Google

Approach

Union-Find on emails; group by root; attach name.

Easy Algorithm

1. map email→id
2. union shared
3. aggregate sorted

Code (Java)

import java.util.*;
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts){Map<String,String> parent=new HashMap<>();Map<String,String> emailName=new HashMap<>();
java.util.function.Function<String,String> find=new java.util.function.Function<>(){public String apply(String x){parent.putIfAbsent(x,x);if(!parent.get(x).equals(x))parent.put(x,apply(parent.get(x)));return parent.get(x);}};
for(List<String> acc:accounts){String name=acc.get(0);for(int i=1;i<acc.size();i++){emailName.put(acc.get(i),name);parent.putIfAbsent(acc.get(i),acc.get(i));
String a=find.apply(acc.get(1)),b=find.apply(acc.get(i));parent.put(b,a);}}
Map<String,TreeSet<String>> groups=new HashMap<>();for(String e:emailName.keySet())groups.computeIfAbsent(find.apply(e),k->new TreeSet<>()).add(e);
List<List<String>> res=new ArrayList<>();for(var en:groups.entrySet()){List<String> row=new ArrayList<>();row.add(emailName.get(en.getValue().first()));row.addAll(en.getValue());res.add(row);}
return res;}
  public static void main(String[] args) {
    System.out.println(new Solution().accountsMerge(/*...*/));
  }
}

Design sketch. This outline shows structure only and is not meant to run as a single file, so it has no Run button. Use Copy to keep it as a starting point.

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

classic LC merge

Also asked: Amazon, Meta

Approach

Expand right to satisfy need; shrink left; track best window.

Easy Algorithm

1. need map + missing count
2. move R; while valid move L; update best

Code (Java)

// Imports Java utility classes for collections and other utilities.
import java.util.*;
// Defines the Main class containing the program entry point.
public class Main {
    // Main method where program execution begins.
    public static void main(String[] args) {
        // Creates an instance of Solution to call minWindow.
        Solution sol = new Solution();
        // Calls minWindow with sample input and stores the result.
        String result = sol.minWindow("ADOBECODEBANC", "ABC");
        // Prints the result of the first test case.
        System.out.println("Result: " + result);
        // Prints the result of a second test case with single character.
        System.out.println("Test2: " + sol.minWindow("a", "a"));
    }
}
// Defines the Solution class containing the minWindow algorithm.
class Solution {
// Declares minWindow method; initializes character needs array and missing count.
public String minWindow(String s,String t){int[] need=new int[128];int missing=t.length();
// Builds frequency map of characters needed from t; initializes best window indices and left pointer.
for(char c:t.toCharArray())need[c]++;int bestL=0,bestR=Integer.MAX_VALUE,L=0;
// Expands the window to the right, updating missing count and character needs.
for(int R=0;R<s.length();R++){char c=s.charAt(R);if(need[c]>0)missing--;need[c]--;
// Shrinks the window from the left while all characters are satisfied, updating best window.
while(missing==0){if(R-L<bestR-bestL){bestL=L;bestR=R;}need[s.charAt(L)]++;if(need[s.charAt(L)]>0)missing++;L++;}}
// Returns the smallest valid window substring or empty string if none found.
return bestR==Integer.MAX_VALUE?"":s.substring(bestL,bestR+1);}
  // Additional main method in Solution for standalone testing.
  public static void main(String[] args) {
    // Runs a test case and prints the result directly.
    System.out.println(new Solution().minWindow("ADOBECODEBANC","ABC"));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

s=ADOBECODEBANC t=ABC → BANC

Also asked: Amazon, Google

Approach

Track farthest reachable index while scanning; fail if i exceeds farthest.

Easy Algorithm

1. farthest=0
2. for i: if i>farthest return false; farthest=max(farthest,i+nums[i])
3. return true

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test case 1: can reach end
        int[] nums1 = {2, 3, 1, 1, 4};
        System.out.println("Test 1: " + sol.canJump(nums1)); // true
        // Test case 2: cannot reach end
        int[] nums2 = {3, 2, 1, 0, 4};
        System.out.println("Test 2: " + sol.canJump(nums2)); // false
        // Test case 3: single element
        int[] nums3 = {0};
        System.out.println("Test 3: " + sol.canJump(nums3)); // true
    }
}

class Solution {
public boolean canJump(int[] nums){int far=0;for(int i=0;i<nums.length;i++){if(i>far)return false;far=Math.max(far,i+nums[i]);}return true;}
  public static void main(String[] args){System.out.println(new Solution().canJump(new int[]{2,3,1,1,4}));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

If total gas<cost impossible. Reset start when tank goes negative.

Easy Algorithm

1. if sum gas<cost return -1
2. tank=0 start=0
3. for i: tank+=gas-cost; if tank<0: start=i+1 tank=0

Code (Java)

import java.util.*;
public class Main {
    /**
     * Main class to demonstrate the gas station circuit problem.
     */
    public static void main(String[] args) {
        // Create an instance of Solution to use its method
        Solution sol = new Solution();
        // Sample gas and cost arrays
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        // Call the method and print the starting index
        int result = sol.canCompleteCircuit(gas, cost);
        System.out.println("Starting index: " + result);
    }
}
class Solution { // Solution class for gas station problem
public int canCompleteCircuit(int[] gas,int[] cost){int total=0,tank=0,start=0;for(int i=0;i<gas.length;i++){total+=gas[i]-cost[i];tank+=gas[i]-cost[i];if(tank<0){start=i+1;tank=0;}}return total<0?-1:start;} // greedy algorithm to find starting index
  public static void main(String[] args){System.out.println(new Solution().canCompleteCircuit(new int[]{1,2,3,4,5},new int[]{3,4,5,1,2}));} // demo main method
} // end of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Put in set; only start streak when num-1 absent; count forward.

Easy Algorithm

1. set=all
2. start only if x-1 missing
3. extend while x+len present; track max

Code (Java)

import java.util.*;
// Main class to demonstrate the longestConsecutive algorithm
public class Main {
    // Entry point: runs demo test cases
    public static void main(String[] args) {
        Solution sol = new Solution(); // Create Solution instance
        int[] test1 = {100, 4, 200, 1, 3, 2}; // Example with streak 1-4
        System.out.println("Test 1: " + sol.longestConsecutive(test1)); // Expected: 4
        int[] test2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1}; // Example with streak 0-8
        System.out.println("Test 2: " + sol.longestConsecutive(test2)); // Expected: 9
        int[] test3 = {}; // Empty array edge case
        System.out.println("Test 3: " + sol.longestConsecutive(test3)); // Expected: 0
    }
}
// Solution class containing the O(n) longest consecutive sequence algorithm
class Solution {
public int longestConsecutive(int[] nums){Set<Integer> s=new HashSet<>();for(int n:nums)s.add(n);int best=0;for(int n:s){if(!s.contains(n-1)){int len=1;while(s.contains(n+len))len++;best=Math.max(best,len);}}return best;} // Core algorithm: hash set streaks
  public static void main(String[] args){System.out.println(new Solution().longestConsecutive(new int[]{100,4,200,1,3,2}));} // Snippet's own demo main
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Stack (prev,k); on ] expand chunk.repeat(k) onto prev.

Easy Algorithm

1. parse digits to k
2. [: push buf+k reset
3. ]: pop expand
4. else append

Code (Java)

import java.util.*;
public class Main {
    /**
     * Main class to demonstrate the decodeString functionality.
     */
    public static void main(String[] args) {
        Solution solver = new Solution(); // create instance of Solution
        // Test case 1: nested encoding
        String input1 = "3[a2[c]]";
        String output1 = solver.decodeString(input1);
        System.out.println("Input: " + input1 + " -> Output: " + output1); // expected: accaccacc
        // Test case 2: simple encoding
        String input2 = "2[abc]3[cd]ef";
        String output2 = solver.decodeString(input2);
        System.out.println("Input: " + input2 + " -> Output: " + output2); // expected: abcabccdcdcdef
        // Test case 3: no encoding
        String input3 = "abc";
        String output3 = solver.decodeString(input3);
        System.out.println("Input: " + input3 + " -> Output: " + output3); // expected: abc
    }
}
/**
 * Solution class containing the decodeString method to decode nested k[encoded] patterns.
 */
class Solution {
public String decodeString(String s){Deque<Integer> ks=new ArrayDeque<>();Deque<StringBuilder> strs=new ArrayDeque<>();StringBuilder cur=new StringBuilder();int k=0; // decode method
for(char c:s.toCharArray()){if(Character.isDigit(c))k=k*10+c-'0';else if(c=='['){ks.push(k);strs.push(cur);cur=new StringBuilder();k=0;}else if(c==']'){StringBuilder prev=strs.pop();int rep=ks.pop();for(int i=0;i<rep;i++)prev.append(cur);cur=prev;}else cur.append(c);}return cur.toString();} // decode logic
  public static void main(String[] args){System.out.println(new Solution().decodeString("3[a2[c]]"));} // snippet's own main
} // end of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Push; on left-mover collide while top is right-moving.

Easy Algorithm

1. for each asteroid
2. while opposite collision: compare abs
3. push survivor

Code (Java)

import java.util.*;

/**
 * Main class demonstrating the asteroid collision solution.
 */
public class Main {
    /**
     * Entry point: runs several test cases for asteroidCollision.
     */
    public static void main(String[] args) { // Demo asteroidCollision with sample data
        Solution sol = new Solution(); // Create solution instance
        int[] result1 = sol.asteroidCollision(new int[]{5, 10, -5}); // Test case 1
        System.out.println("Test 1: " + Arrays.toString(result1)); // Print result
        int[] result2 = sol.asteroidCollision(new int[]{8, -8}); // Test case 2
        System.out.println("Test 2: " + Arrays.toString(result2)); // Print result
        int[] result3 = sol.asteroidCollision(new int[]{10, 2, -5}); // Test case 3
        System.out.println("Test 3: " + Arrays.toString(result3)); // Print result
    }
}
class Solution { // Snippet class for asteroid collision logic
public int[] asteroidCollision(int[] asteroids){Deque<Integer> st=new ArrayDeque<>();for(int a:asteroids){boolean push=true;while(!st.isEmpty()&&st.peek()>0&&a<0){int top=st.peek();if(top<-a){st.pop();continue;}if(top==-a)st.pop();push=false;break;}if(push)st.push(a);}int[] res=new int[st.size()];for(int i=res.length-1;i>=0;i--)res[i]=st.pop();return res;} // Core algorithm using stack
  public static void main(String[] args){System.out.println(Arrays.toString(new Solution().asteroidCollision(new int[]{5,10,-5})));} // Snippet's own main method
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Frame from max freq; fill idle with other tasks; ans=len+remaining idle.

Easy Algorithm

1. f=max freq
2. idle=(f-1)*n
3. subtract other fills
4. return n+max(0,idle)

Code (Java)

import java.util.*;

// Main class to demonstrate the task scheduler solution
public class Main {
    public static void main(String[] args) {
        Solution solver = new Solution(); // Create instance of Solution
        // Test case 1: tasks = ["A","A","A","B","B","B"], n = 2
        char[] tasks1 = {'A','A','A','B','B','B'};
        int n1 = 2;
        int result1 = solver.leastInterval(tasks1, n1);
        System.out.println("Test 1 (AAA BBB, n=2): " + result1); // Expected 8
        
        // Test case 2: tasks = ["A","A","A","B","B","B"], n = 0
        char[] tasks2 = {'A','A','A','B','B','B'};
        int n2 = 0;
        int result2 = solver.leastInterval(tasks2, n2);
        System.out.println("Test 2 (AAA BBB, n=0): " + result2); // Expected 6
        
        // Test case 3: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
        char[] tasks3 = {'A','A','A','A','A','A','B','C','D','E','F','G'};
        int n3 = 2;
        int result3 = solver.leastInterval(tasks3, n3);
        System.out.println("Test 3 (6A + BCDEFG, n=2): " + result3); // Expected 16
    }
}

// Solution class implementing the leastInterval method for task scheduling with cooldown
class Solution {
public int leastInterval(char[] tasks,int n){int[] cnt=new int[26];for(char c:tasks)cnt[c-'A']++;Arrays.sort(cnt);int f=cnt[25];int idle=(f-1)*n;for(int i=24;i>=0&&cnt[i]>0;i--)idle-=Math.min(cnt[i],f-1);return tasks.length+Math.max(0,idle);} // Count frequencies, sort, calculate idle slots
  public static void main(String[] args){System.out.println(new Solution().leastInterval(new char[]{'A','A','A','B','B','B'},2));} // Original snippet main method
} // End of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Target=sum/2; DP reachable sums with boolean array (or bitset).

Easy Algorithm

1. if sum odd false
2. dp[0]=true
3. for num: update dp backward
4. return dp[target]

Code (Java)

import java.util.*;

/**
 * Main class to demonstrate the canPartition method.
 */
public class Main {
    /**
     * Entry point: runs several test cases for the partition equal subset sum problem.
     */
    public static void main(String[] args) {
        Solution sol = new Solution(); // create instance of Solution
        // Test case 1: can partition into {1,5,5} and {11}
        int[] nums1 = {1, 5, 11, 5};
        System.out.println("Test 1 (expect true): " + sol.canPartition(nums1));
        // Test case 2: cannot partition
        int[] nums2 = {1, 2, 3, 5};
        System.out.println("Test 2 (expect false): " + sol.canPartition(nums2));
        // Test case 3: single element
        int[] nums3 = {2};
        System.out.println("Test 3 (expect false): " + sol.canPartition(nums3));
        // Test case 4: empty array (sum=0, trivially partitionable)
        int[] nums4 = {};
        System.out.println("Test 4 (expect true): " + sol.canPartition(nums4));
    }
}

/**
 * Solution class containing the 0/1 knapsack DP for partition equal subset sum.
 */
class Solution {
public boolean canPartition(int[] nums){int sum=0;for(int n:nums)sum+=n;if((sum&1)==1)return false;int t=sum/2;boolean[] dp=new boolean[t+1];dp[0]=true;for(int n:nums)for(int s=t;s>=n;s--)dp[s]|=dp[s-n];return dp[t];} // DP solution
  public static void main(String[] args){System.out.println(new Solution().canPartition(new int[]{1,5,11,5}));} // original demo
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Outer coins / inner amounts — order ensures combinations not permutations.

Easy Algorithm

1. dp[0]=1
2. for coin: for a=coin..amount: dp[a]+=dp[a-coin]
3. return dp[amount]

Code (Java)

import java.util.*;

// Main class to demonstrate the Coin Change II solution
public class Main {
    public static void main(String[] args) {
        // Create an instance of Solution
        Solution sol = new Solution();
        // Sample amount and coins
        int amount = 5;
        int[] coins = {1, 2, 5};
        // Compute the number of ways to make change
        int result = sol.change(amount, coins);
        // Print the result
        System.out.println("Number of ways to make change for " + amount + " with coins " + Arrays.toString(coins) + ": " + result);
    }
}

// Solution class implementing the coin change algorithm (unbounded knapsack DP)
class Solution {
public int change(int amount,int[] coins){int[] dp=new int[amount+1];dp[0]=1;for(int c:coins)for(int a=c;a<=amount;a++)dp[a]+=dp[a-c];return dp[amount];} // DP solution for coin change II
  public static void main(String[] args){System.out.println(new Solution().change(5,new int[]{1,2,5}));} // Example usage from the snippet
} // End of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

dp[0][0]=1 if free; first row/col blocked propagate; dp[i][j]=sum from up/left if free.

Easy Algorithm

1. if start blocked 0
2. init borders until obstacle
3. dp cells = up+left if empty

Code (Java)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution(); // Create Solution instance
        int[][] grid1 = {{0,0,0},{0,1,0},{0,0,0}}; // 3x3 grid with obstacle at center
        System.out.println("Grid 3x3 with center obstacle: " + sol.uniquePathsWithObstacles(grid1));
        int[][] grid2 = {{0}}; // 1x1 grid no obstacle
        System.out.println("1x1 no obstacle: " + sol.uniquePathsWithObstacles(grid2));
        int[][] grid3 = {{1}}; // 1x1 grid with obstacle
        System.out.println("1x1 with obstacle: " + sol.uniquePathsWithObstacles(grid3));
        int[][] grid4 = {{0,0},{0,0}}; // 2x2 grid no obstacles
        System.out.println("2x2 no obstacles: " + sol.uniquePathsWithObstacles(grid4));
    }
}
class Solution {
public int uniquePathsWithObstacles(int[][] g){int m=g.length,n=g[0].length;if(g[0][0]==1)return 0;int[][] dp=new int[m][n];dp[0][0]=1; // Initialize DP, return 0 if start blocked
for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(g[i][j]==1){dp[i][j]=0;continue;}if(i==0&&j==0)continue;int up=i>0?dp[i-1][j]:0,left=j>0?dp[i][j-1]:0;dp[i][j]=up+left;}return dp[m-1][n-1];} // DP fill: skip obstacles, sum from up and left
  public static void main(String[] args){System.out.println(new Solution().uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));} // Original snippet demo
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

dp[i][j]=grid+min(up,left) with border prefix fills.

Easy Algorithm

1. dp[0][0]=grid
2. fill first row/col cumulatively
3. interior = cell+min(up,left)

Code (Java)

import java.util.*;
// Main class to demonstrate the minimum path sum algorithm
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int result = sol.minPathSum(grid);
        System.out.println("Min path sum: " + result);
    }
}
class Solution {
public int minPathSum(int[][] g){int m=g.length,n=g[0].length;int[][] dp=new int[m][n];dp[0][0]=g[0][0]; // initialize dp grid and set starting cell
for(int i=1;i<m;i++)dp[i][0]=dp[i-1][0]+g[i][0];for(int j=1;j<n;j++)dp[0][j]=dp[0][j-1]+g[0][j]; // fill first column and first row
for(int i=1;i<m;i++)for(int j=1;j<n;j++)dp[i][j]=g[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);return dp[m-1][n-1];} // fill rest of dp grid and return bottom-right value
  public static void main(String[] args){System.out.println(new Solution().minPathSum(new int[][]{{1,3,1},{1,5,1},{4,2,1}}));} // demo main in Solution class
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Three pointers lo/mid/hi; swap 0s left, 2s right, advance on 1.

Easy Algorithm

1. lo=0 mid=0 hi=n-1
2. while mid<=hi: 0→swap lo++; 2→swap hi--; 1→mid++

Code (Java)

// Import Java utility classes including Arrays for printing arrays.
import java.util.*;
// Define the Main class containing the program entry point.
public class Main {
    // Main method that runs the test cases.
    public static void main(String[] args) {
        // Create an instance of the Solution class to call sortColors.
        Solution sol = new Solution();
        // First test input array containing 0s, 1s, and 2s in random order.
        int[] test1 = {2,0,2,1,1,0};
        // Call sortColors on test1 and store the sorted result.
        int[] result1 = sol.sortColors(test1);
        // Print the sorted array for test 1.
        System.out.println("Test 1: " + Arrays.toString(result1));
        // Second test input array with a different arrangement.
        int[] test2 = {2,2,1,0,1,0};
        // Call sortColors on test2 and store the sorted result.
        int[] result2 = sol.sortColors(test2);
        // Print the sorted array for test 2.
        System.out.println("Test 2: " + Arrays.toString(result2));
    }
}
// Solution class containing the sorting algorithm implementation.
class Solution {
// sortColors method using Dutch National Flag algorithm with three pointers (lo, mid, hi) to sort 0s, 1s, 2s in-place in a single pass.
public int[] sortColors(int[] nums){int lo=0,mid=0,hi=nums.length-1;while(mid<=hi){if(nums[mid]==0){int t=nums[lo];nums[lo]=nums[mid];nums[mid]=t;lo++;mid++;}else if(nums[mid]==2){int t=nums[hi];nums[hi]=nums[mid];nums[mid]=t;hi--;}else mid++;}return nums;}
  // Additional main method inside Solution for standalone demonstration.
  public static void main(String[] args){System.out.println(Arrays.toString(new Solution().sortColors(new int[]{2,0,2,1,1,0})));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Max-heap by distance keep size k; or quickselect.

Easy Algorithm

1. push points to max-heap by dist
2. pop when size>k
3. return heap contents

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) { // demo kClosest with sample data
        Solution sol = new Solution();
        int[][] points = {{3,3}, {5,-1}, {-2,4}, {0,1}, {-1,0}};
        int k = 3;
        int[][] result = sol.kClosest(points, k);
        System.out.println("K closest points: " + Arrays.deepToString(result));
    }
}

class Solution { // solution class for k closest points
public int[][] kClosest(int[][] points,int k){PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->Long.compare((long)b[0]*b[0]+(long)b[1]*b[1],(long)a[0]*a[0]+(long)a[1]*a[1])); // max-heap by distance squared
for(int[] p:points){pq.offer(p);if(pq.size()>k)pq.poll();}return pq.toArray(new int[0][]);} // keep only k closest
  public static void main(String[] args){System.out.println(Arrays.deepToString(new Solution().kClosest(new int[][]{{1,3},{-2,2}},1)));} // original demo
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Uber

Approach

DFS/BFS 4-dir from start; only recolor original color cells.

Easy Algorithm

1. save old color; if same as new return
2. DFS 4-dir when in-bound and ==old
3. set newColor

Code (Java)

import java.util.*;
/*
 * Main entry point: demonstrates the floodFill algorithm on a sample image grid.
 */
public class Main {
    public static void main(String[] args) { // program starts here
        Solution sol = new Solution(); // create solution instance
        int[][] image = {{1,1,1},{1,1,0},{1,0,1}}; // 3x3 input grid
        int[][] result = sol.floodFill(image, 1, 1, 2); // fill from center (1,1) with color 2
        System.out.println(Arrays.deepToString(result)); // print resulting grid
    }
}
/*
 * Solution class containing the floodFill implementation using depth-first search.
 */
class Solution {
public int[][] floodFill(int[][] image,int sr,int sc,int color){int old=image[sr][sc];if(old==color)return image;dfs(image,sr,sc,old,color);return image;} // entry: capture original color, early exit if same, start DFS
void dfs(int[][] g,int r,int c,int old,int col){if(r<0||c<0||r>=g.length||c>=g[0].length||g[r][c]!=old)return;g[r][c]=col;dfs(g,r+1,c,old,col);dfs(g,r-1,c,old,col);dfs(g,r,c+1,old,col);dfs(g,r,c-1,old,col);} // DFS: bounds & color check, paint, recurse 4 directions
  public static void main(String[] args){System.out.println(Arrays.deepToString(new Solution().floodFill(new int[][]{{1,1,1},{1,1,0},{1,0,1}},1,1,2)));} // self-test main (not used when run via Main)
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

DFS each unvisited 1; sum area; track global max.

Easy Algorithm

1. scan cells
2. on land: dfs mark 0 and return 1+neighbors
3. track max area

Code (Java)

// Imports Java utility classes for collections and other utilities.
import java.util.*;
// Defines the Main class containing the program entry point.
public class Main {
    // Main method where program execution begins.
    public static void main(String[] args) {
        // Demo maxAreaOfIsland with sample grid
        // Creates an instance of the Solution class to access its methods.
        Solution sol = new Solution();
        // Initializes a 2D grid representing water (0) and land (1) for testing.
        int[][] grid = {{0,0,1,0,0},{0,0,0,0,0},{0,0,1,1,1}};
        // Calls maxAreaOfIsland to compute the largest island area in the grid.
        int result = sol.maxAreaOfIsland(grid);
        // Outputs the computed maximum island area to the console.
        System.out.println("Max area of island: " + result);
    }
}

// Defines the Solution class containing the island area calculation logic.
class Solution {
// Public method that scans the grid and uses DFS to find the maximum island area.
public int maxAreaOfIsland(int[][] g){int best=0;for(int r=0;r<g.length;r++)for(int c=0;c<g[0].length;c++)if(g[r][c]==1)best=Math.max(best,dfs(g,r,c));return best;}
// Private DFS helper that recursively explores connected land cells, marking them visited by setting to 0, and returns the area of the current island.
int dfs(int[][] g,int r,int c){if(r<0||c<0||r>=g.length||c>=g[0].length||g[r][c]==0)return 0;g[r][c]=0;return 1+dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);}
  // Additional main method inside Solution for standalone testing of the algorithm.
  public static void main(String[] args){System.out.println(new Solution().maxAreaOfIsland(new int[][]{{0,0,1,0,0},{0,0,0,0,0},{0,0,1,1,1}}));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

BFS/DFS from 0 collecting keys; visited size==n.

Easy Algorithm

1. queue/stack from 0
2. visit + enqueue keys
3. return visited==n

Code (Java)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test case 1: can visit all rooms
        List<List<Integer>> rooms1 = List.of(List.of(1), List.of(2), List.of(3), List.of());
        System.out.println("Test 1 (expect true): " + sol.canVisitAllRooms(rooms1));
        // Test case 2: cannot visit all rooms (room 2 unreachable)
        List<List<Integer>> rooms2 = List.of(List.of(1), List.of(), List.of(3), List.of());
        System.out.println("Test 2 (expect false): " + sol.canVisitAllRooms(rooms2));
        // Test case 3: single room
        List<List<Integer>> rooms3 = List.of(List.of());
        System.out.println("Test 3 (expect true): " + sol.canVisitAllRooms(rooms3));
    }
}
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms){boolean[] seen=new boolean[rooms.size()];Deque<Integer> q=new ArrayDeque<>();q.add(0);seen[0]=true;int vis=1; // BFS initialization
while(!q.isEmpty()){int u=q.poll();for(int k:rooms.get(u))if(!seen[k]){seen[k]=true;vis++;q.add(k);}}return vis==rooms.size();} // BFS loop and result
  public static void main(String[] args){System.out.println(new Solution().canVisitAllRooms(List.of(List.of(1),List.of(2),List.of(3),List.of())));} // Original demo main
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

BFS/DFS 2-color each component; conflict ⇒ false.

Easy Algorithm

1. color array -1
2. BFS assign opposite color to neighbors
3. conflict if same

Code (Java)

import java.util.*;

/** Main class to demonstrate the Solution.isBipartite method. */
public class Main {
    /** Runs demonstration of bipartite graph checking. */
    public static void main(String[] args) {
        // Demo 1: bipartite graph (even cycle)
        int[][] graph1 = {{1,3}, {0,2}, {1,3}, {0,2}};
        Solution sol = new Solution();
        System.out.println("Graph1 (even cycle) is bipartite: " + sol.isBipartite(graph1));
        // Demo 2: non-bipartite graph (odd cycle)
        int[][] graph2 = {{1,2,3}, {0,2}, {0,1,3}, {0,2}};
        System.out.println("Graph2 (odd cycle) is bipartite: " + sol.isBipartite(graph2));
    }
}

class Solution {
public boolean isBipartite(int[][] graph){int n=graph.length;int[] col=new int[n];Arrays.fill(col,-1);
for(int i=0;i<n;i++){if(col[i]!=-1)continue;Deque<Integer> q=new ArrayDeque<>();q.add(i);col[i]=0;
while(!q.isEmpty()){int u=q.poll();for(int v:graph[u]){if(col[v]==-1){col[v]=col[u]^1;q.add(v);}else if(col[v]==col[u])return false;}}}return true;}
  public static void main(String[] args){System.out.println(new Solution().isBipartite(new int[][]{{1,2,3},{0,2},{0,1,3},{0,2}}));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Kahn BFS: indegrees, queue zeros, append order; if count<n cycle.

Easy Algorithm

1. build graph+indegree
2. queue indegree0
3. pop append; reduce neighbors

Code (Java)

// Imports Java utility classes like ArrayList, Deque, and Arrays for data structures and printing.
import java.util.*;
// Defines the Main class containing the program entry point.
public class Main {
    // Main method that runs the demo for the course schedule problem.
    public static void main(String[] args) {
        // Creates an instance of Solution to call the topological sort method.
        Solution sol = new Solution();
        // Calls findOrder with 2 courses and one prerequisite: course 1 requires course 0.
        int[] result = sol.findOrder(2, new int[][]{{1,0}});
        // Prints the resulting course order array to the console.
        System.out.println(Arrays.toString(result));
    }
}
// Solution class that implements topological sorting using Kahn's BFS algorithm.
class Solution {
// findOrder method: builds adjacency list g and indegree array ind; initializes empty lists for each node.
public int[] findOrder(int n,int[][] edges){List<List<Integer>> g=new ArrayList<>();int[] ind=new int[n];for(int i=0;i<n;i++)g.add(new ArrayList<>());
// Populates graph edges and indegrees from prerequisites; initializes queue with all zero-indegree nodes.
for(int[] e:edges){g.get(e[1]).add(e[0]);ind[e[0]]++;}Deque<Integer> q=new ArrayDeque<>();for(int i=0;i<n;i++)if(ind[i]==0)q.add(i);
// Processes queue in BFS order, building topological order ord; returns order if all nodes processed, else empty array.
int[] ord=new int[n];int k=0;while(!q.isEmpty()){int u=q.poll();ord[k++]=u;for(int v:g.get(u))if(--ind[v]==0)q.add(v);}return k==n?ord:new int[]{};}
  // Alternative main method inside Solution class for direct testing; prints result for same 2-course example.
  public static void main(String[] args){System.out.println(Arrays.toString(new Solution().findOrder(2,new int[][]{{1,0}})));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

UF with path compression; count roots after unions.

Easy Algorithm

1. parent[i]=i
2. union edges
3. count unique finds

Code (Java)

import java.util.*;
import java.util.function.*;

public class Main {
    // Solution class implements Union-Find (Disjoint Set Union) to count connected components in an undirected graph
    static class Solution {
        // Original countComponents method: initializes parent array, defines find with path compression, unions edges, returns component count
        public int countComponents(int n,int[][] edges){int[] p=new int[n];for(int i=0;i<n;i++)p[i]=i; // Initialize each node as its own parent
        java.util.function.IntUnaryOperator find=new java.util.function.IntUnaryOperator(){public int applyAsInt(int x){return p[x]==x?x:(p[x]=applyAsInt(p[x]));}}; // Find with path compression
        int c=n;for(int[] e:edges){int a=find.applyAsInt(e[0]),b=find.applyAsInt(e[1]);if(a!=b){p[a]=b;c--;}}return c;} // Union each edge, decrement count when merging
          public static void main(String[] args){System.out.println(new Solution().countComponents(5,new int[][]{{0,1},{1,2},{3,4}}));} // Original test case
    }

    // Main entry point: exercises Solution with the same sample graph and prints result
    public static void main(String[] args) {
        Solution solution = new Solution();
        int components = solution.countComponents(5, new int[][]{{0,1},{1,2},{3,4}});
        System.out.println("Number of connected components: " + components); // Expected output: 2
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Union edges; first already-connected edge is answer.

Easy Algorithm

1. UF
2. if same root return edge
3. else union

Code (Java)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] edges1 = {{1,2},{1,3},{2,3}};
        System.out.println(Arrays.toString(sol.findRedundantConnection(edges1))); // [2, 3]
        int[][] edges2 = {{1,2},{2,3},{3,4},{1,4},{1,5}};
        System.out.println(Arrays.toString(sol.findRedundantConnection(edges2))); // [1, 4]
    }
}
class Solution {
public int[] findRedundantConnection(int[][] edges){int n=edges.length;int[] p=new int[n+1];for(int i=0;i<=n;i++)p[i]=i; // initialize parent array
java.util.function.IntUnaryOperator find=new java.util.function.IntUnaryOperator(){public int applyAsInt(int x){return p[x]==x?x:(p[x]=applyAsInt(p[x]));}}; // find with path compression
for(int[] e:edges){int a=find.applyAsInt(e[0]),b=find.applyAsInt(e[1]);if(a==b)return e;p[a]=b;}return new int[]{};} // union-find cycle detection
  public static void main(String[] args){System.out.println(Arrays.toString(new Solution().findRedundantConnection(new int[][]{{1,2},{1,3},{2,3}})));} // original demo
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Dijkstra from k; answer max dist among reachable.

Easy Algorithm

1. adj + minheap
2. relax
3. max dist or -1

Code (Java)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4;
        int k = 2;
        int result = sol.networkDelayTime(times, n, k);
        System.out.println("Network delay time: " + result);
    }
}
class Solution {
public int networkDelayTime(int[][] times,int n,int k){List<int[]>[] g=new ArrayList[n+1];for(int i=1;i<=n;i++)g[i]=new ArrayList<>(); // Build graph adjacency list
for(int[] t:times)g[t[0]].add(new int[]{t[1],t[2]});int[] dist=new int[n+1];Arrays.fill(dist,Integer.MAX_VALUE);dist[k]=0; // Add edges, init distances, source distance = 0
PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));pq.offer(new int[]{0,k}); // Min-heap by distance, start from source
while(!pq.isEmpty()){int[] cur=pq.poll();int d=cur[0],u=cur[1];if(d!=dist[u])continue;for(int[] e:g[u]){int v=e[0],w=e[1];if(dist[v]>d+w){dist[v]=d+w;pq.offer(new int[]{dist[v],v});}}} // Dijkstra main loop
int ans=0;for(int i=1;i<=n;i++){if(dist[i]==Integer.MAX_VALUE)return -1;ans=Math.max(ans,dist[i]);}return ans;} // Find max delay or -1 if any node unreachable
  public static void main(String[] args){System.out.println(new Solution().networkDelayTime(new int[][]{{2,1,1},{2,3,1},{3,4,1}},4,2));} // Original demo
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Bellman-Ford k+1 rounds with snapshot array.

Easy Algorithm

1. dist[src]=0
2. relax k+1 times from snapshot
3. return dist[dst]

Code (Java)

import java.util.*;

/* Main class to demonstrate the cheapest flights solution */
public class Main {
    /* Demonstrates finding cheapest price with up to k stops */
    public static void main(String[] args) {
        Solution sol = new Solution();
        int n = 4;
        int[][] flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
        int src = 0, dst = 3, k = 1;
        int result = sol.findCheapestPrice(n, flights, src, dst, k);
        System.out.println("Cheapest price: " + result);
    }
}

/* Solution class implementing Bellman-Ford for cheapest flights within k stops */
class Solution { // Solution class for cheapest flights
public int findCheapestPrice(int n,int[][] flights,int src,int dst,int k){int[] dist=new int[n];Arrays.fill(dist,Integer.MAX_VALUE/4);dist[src]=0; // Initialize distances
for(int i=0;i<=k;i++){int[] next=dist.clone();for(int[] f:flights){int u=f[0],v=f[1],w=f[2];if(dist[u]+w<next[v])next[v]=dist[u]+w;}dist=next;} // Relax edges up to k+1 times
return dist[dst]>=Integer.MAX_VALUE/4?-1:dist[dst];} // Return -1 if unreachable
  public static void main(String[] args){System.out.println(new Solution().findCheapestPrice(4,new int[][]{{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}},0,3,1));} // Demo main
} // End of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Equal-weight grid path ⇒ BFS (8-connected). Mark visited when enqueued to avoid duplicates; first time you reach the end is the shortest length (Job Prep matrix/BFS pattern family with Islands/Oranges).

Easy Algorithm

1. If start or end blocked ⇒ -1; n=1 ⇒ 1.
2. BFS from (0,0) with dist=1; explore 8 neighbors that are 0.
3. Mark cell visited on enqueue; return dist when (n-1,n-1) reached.

Code (Java)

// Imports Java utility classes for collections.
import java.util.*;
// Main class containing test cases for the solution.
public class Main {
    // Entry point that runs test cases for the shortest path algorithm.
    public static void main(String[] args) {
        // Create an instance of Solution to call the method.
        Solution sol = new Solution();
        // Test case 1: 2x2 matrix with diagonal path
        // Initialize a 2x2 grid with a diagonal clear path.
        int[][] grid1 = {{0,1},{1,0}};
        // Run test 1 and print result, expecting path length 2.
        System.out.println("Test 1 (expect 2): " + sol.shortestPathBinaryMatrix(grid1));
        // Test case 2: 1x1 matrix with 0
        // Initialize a 1x1 grid with a single clear cell.
        int[][] grid2 = {{0}};
        // Run test 2 and print result, expecting 1.
        System.out.println("Test 2 (expect 1): " + sol.shortestPathBinaryMatrix(grid2));
        // Test case 3: 1x1 matrix with 1 (blocked)
        // Initialize a 1x1 grid with a blocked cell.
        int[][] grid3 = {{1}};
        // Run test 3 and print result, expecting -1.
        System.out.println("Test 3 (expect -1): " + sol.shortestPathBinaryMatrix(grid3));
        // Test case 4: 3x3 clear path
        // Initialize a 3x3 grid with all cells clear.
        int[][] grid4 = {{0,0,0},{0,0,0},{0,0,0}};
        // Run test 4 and print result, expecting 3.
        System.out.println("Test 4 (expect 3): " + sol.shortestPathBinaryMatrix(grid4));
        // Test case 5: blocked start or end
        // Initialize a 2x2 grid with blocked start cell.
        int[][] grid5 = {{1,0},{0,0}};
        // Run test 5 and print result, expecting -1.
        System.out.println("Test 5 (expect -1): " + sol.shortestPathBinaryMatrix(grid5));
    // End of main method.
    }
// End of Main class.
}
// Solution class containing the shortest path algorithm.
class Solution {
// Method to find shortest clear path in binary matrix using BFS; returns -1 if start or end blocked, 1 for single cell.
public int shortestPathBinaryMatrix(int[][] g){int n=g.length;if(g[0][0]==1||g[n-1][n-1]==1)return -1;if(n==1)return 1;
// Define 8-directional moves, initialize BFS queue with starting cell (0,0) and distance 1, mark start as visited.
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};Deque<int[]> q=new ArrayDeque<>();q.add(new int[]{0,0,1});g[0][0]=1;
// BFS loop: process each cell, explore 8 neighbors, if neighbor is target return distance+1, else mark visited and enqueue with incremented distance; return -1 if no path.
while(!q.isEmpty()){int[] c=q.poll();int r=c[0],co=c[1],d=c[2];for(int[] dir:dirs){int nr=r+dir[0],nc=co+dir[1];if(nr>=0&&nc>=0&&nr<n&&nc<n&&g[nr][nc]==0){if(nr==n-1&&nc==n-1)return d+1;g[nr][nc]=1;q.add(new int[]{nr,nc,d+1});}}}return -1;}
  // Additional main method for quick test (duplicate of test 1).
  public static void main(String[] args){System.out.println(new Solution().shortestPathBinaryMatrix(new int[][]{{0,1},{1,0}}));}
// End of Solution class.
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

DFS uphill from both ocean borders; return intersection.

Easy Algorithm

1. mark Pacific-reachable
2. mark Atlantic-reachable
3. intersect

Code (Java)

import java.util.*;
// Main class to demonstrate the Pacific Atlantic Water Flow solution
public class Main {
    public static void main(String[] args) {
        // Create solution instance
        Solution solution = new Solution();
        // Test case 1: simple 2x2 grid
        int[][] heights1 = {{1,2},{4,3}};
        System.out.println("Test 1: " + solution.pacificAtlantic(heights1));
        // Test case 2: larger grid
        int[][] heights2 = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        System.out.println("Test 2: " + solution.pacificAtlantic(heights2));
    }
}
// Solution class implementing Pacific Atlantic Water Flow using DFS from both oceans
class Solution { // Solution class for water flow problem
public List<List<Integer>> pacificAtlantic(int[][] h){int R=h.length,C=h[0].length;boolean[][] p=new boolean[R][C],a=new boolean[R][C]; // Initialize dimensions and visited arrays for Pacific (p) and Atlantic (a)
for(int r=0;r<R;r++){dfs(h,p,r,0);dfs(h,a,r,C-1);}for(int c=0;c<C;c++){dfs(h,p,0,c);dfs(h,a,R-1,c);} // Start DFS from all border cells touching each ocean
List<List<Integer>> res=new ArrayList<>();for(int r=0;r<R;r++)for(int c=0;c<C;c++)if(p[r][c]&&a[r][c])res.add(List.of(r,c));return res;} // Collect cells reachable from both oceans
void dfs(int[][] h,boolean[][] seen,int r,int c){if(seen[r][c])return;seen[r][c]=true;int[][] d={{1,0},{-1,0},{0,1},{0,-1}}; // DFS with four direction vectors
for(int[] x:d){int nr=r+x[0],nc=c+x[1];if(nr>=0&&nc>=0&&nr<h.length&&nc<h[0].length&&h[nr][nc]>=h[r][c])dfs(h,seen,nr,nc);}} // Recurse to neighbors with equal or higher height
  public static void main(String[] args){System.out.println(new Solution().pacificAtlantic(new int[][]{{1,2},{4,3}}));} // Snippet's own demo main
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

delta[i]+=1 when trusted, -1 when trusts; judge has n-1.

Easy Algorithm

1. apply trust deltas
2. find delta==n-1

Code (Java)

import java.util.*;
// Main class to demonstrate the findJudge solution
public class Main {
    // Entry point: runs sample test cases for the town judge finder
    public static void main(String[] args) {
        Solution sol = new Solution(); // Create solution instance
        // Test case 1: 3 people, 1 and 2 trust 3 -> judge is 3
        System.out.println("Test 1 (expect 3): " + sol.findJudge(3, new int[][]{{1,3},{2,3}}));
        // Test case 2: 4 people, no judge
        System.out.println("Test 2 (expect -1): " + sol.findJudge(4, new int[][]{{1,3},{2,3},{3,1}}));
        // Test case 3: 1 person, no trust -> that person is judge
        System.out.println("Test 3 (expect 1): " + sol.findJudge(1, new int[][]{}));
    }
}
// Solution class implementing the town judge algorithm using in-degree minus out-degree
class Solution { // Solution class from snippet
public int findJudge(int n,int[][] trust){int[] d=new int[n+1];for(int[] t:trust){d[t[0]]--;d[t[1]]++;}for(int i=1;i<=n;i++)if(d[i]==n-1)return i;return -1;} // Finds judge by trust score (in-degree minus out-degree)
  public static void main(String[] args){System.out.println(new Solution().findJudge(3,new int[][]{{1,3},{2,3}}));} // Original snippet demo
} // End of Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Transpose then reverse each row.

Easy Algorithm

1. transpose
2. reverse rows

Code (Java)

import java.util.*;
/* Main class: entry point for the program, demonstrates matrix rotation */
public class Main {
    public static void main(String[] args) {
        // Demo the rotate method with a 3x3 matrix
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        Solution sol = new Solution();
        int[][] rotated = sol.rotate(matrix);
        System.out.println(Arrays.deepToString(rotated));
    }
}
/* Solution class: provides a method to rotate a square matrix 90 degrees clockwise in-place */
class Solution {
public int[][] rotate(int[][] m){int n=m.length;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int t=m[i][j];m[i][j]=m[j][i];m[j][i]=t;} // Transpose the matrix
for(int[] row:m)for(int l=0,r=n-1;l<r;l++,r--){int t=row[l];row[l]=row[r];row[r]=t;}return m;} // Reverse each row
  public static void main(String[] args){System.out.println(Arrays.deepToString(new Solution().rotate(new int[][]{{1,2,3},{4,5,6},{7,8,9}})));} // Demo main
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Use first row/col as markers; second pass apply.

Easy Algorithm

1. mark with first row/col
2. apply markers
3. zero borders if needed

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] matrix = {{1,1,1},{1,0,1},{1,1,1}};
        Solution sol = new Solution();
        int[][] result = sol.setZeroes(matrix);
        System.out.println(Arrays.deepToString(result));
    }
}
class Solution {
public int[][] setZeroes(int[][] m){int R=m.length,C=m[0].length;boolean fr=false,fc=false; // initialize dimensions and flags
for(int c=0;c<C;c++)if(m[0][c]==0)fr=true;for(int r=0;r<R;r++)if(m[r][0]==0)fc=true; // check first row and column for zeros
for(int r=1;r<R;r++)for(int c=1;c<C;c++)if(m[r][c]==0){m[r][0]=0;m[0][c]=0;} // mark rows and columns using first row/col
for(int r=1;r<R;r++)for(int c=1;c<C;c++)if(m[r][0]==0||m[0][c]==0)m[r][c]=0; // zero cells based on marks
if(fr)for(int c=0;c<C;c++)m[0][c]=0;if(fc)for(int r=0;r<R;r++)m[r][0]=0;return m;} // zero first row/col if needed
  public static void main(String[] args){System.out.println(Arrays.deepToString(new Solution().setZeroes(new int[][]{{1,1,1},{1,0,1},{1,1,1}})));} // demo main
} // end class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Boolean maps for rows, cols, boxes (r/3*3+c/3).

Easy Algorithm

1. skip dots
2. box index
3. reject dups

Code (Java)

// Import Java utility classes for collections.
import java.util.*;
// Define the Main class containing the demonstration entry point.
public class Main {
    // Main method starts; args unused.
    public static void main(String[] args) {
        // valid board
        // Array of strings representing a valid Sudoku board rows.
        String[] validRows = {
            "53..7....",
            "6..195...",
            ".98....6.",
            "8...6...3",
            "4..8.3..1",
            "7...2...6",
            ".6....28.",
            "...419..5",
            "....8..79"
        };
        // Create 9x9 char array to hold the valid board.
        char[][] validBoard = new char[9][9];
        // Loop over each row index.
        for (int i = 0; i < 9; i++) {
            // Convert each string row to char array and store.
            validBoard[i] = validRows[i].toCharArray();
        }
        // invalid board: duplicate '5' in first row
        String[] invalidRows = {
            "55..7....",
            "6..195...",
            ".98....6.",
            "8...6...3",
            "4..8.3..1",
            "7...2...6",
            ".6....28.",
            "...419..5",
            "....8..79"
        };
        // Create 9x9 char array for the invalid board.
        char[][] invalidBoard = new char[9][9];
        // Loop over each row index.
        for (int i = 0; i < 9; i++) {
            // Convert each string row to char array and store.
            invalidBoard[i] = invalidRows[i].toCharArray();
        }
        // Instantiate Solution to validate boards.
        Solution solver = new Solution();
        // Print validation result for the valid board.
        System.out.println("Valid board: " + solver.isValidSudoku(validBoard));
        // Print validation result for the invalid board.
        System.out.println("Invalid board: " + solver.isValidSudoku(invalidBoard));
    }
}
// Solution class containing Sudoku validation logic.
class Solution {
// isValidSudoku method: uses three boolean 9x9 arrays to track digits seen in rows, columns, and 3x3 boxes.
public boolean isValidSudoku(char[][] board){boolean[][] rows=new boolean[9][9],cols=new boolean[9][9],boxes=new boolean[9][9];
// Iterate every cell; skip '.'; compute digit index and box index; if digit already seen in row, column, or box return false; otherwise mark seen.
for(int r=0;r<9;r++)for(int c=0;c<9;c++){if(board[r][c]=='.')continue;int d=board[r][c]-'1';int b=(r/3)*3+c/3;if(rows[r][d]||cols[c][d]||boxes[b][d])return false;rows[r][d]=cols[c][d]=boxes[b][d]=true;}return true;}
  // Return true if no duplicates found.
  public static void main(String[] args){System.out.println("ok");}
// Unused main method in Solution class.
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Place each value v at index v-1 via swaps; scan for first mismatch.

Easy Algorithm

1. swap nums[i] into place while in range
2. scan for nums[i]!=i+1
3. else return n+1

Code (Java)

import java.util.*;

public class Main {
    // Solution class implementing the first missing positive algorithm via cyclic sort
    static class Solution {
        // Finds the smallest missing positive integer by placing each value v at index v-1
        public int firstMissingPositive(int[] nums){int n=nums.length;for(int i=0;i<n;i++)while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){int j=nums[i]-1;int t=nums[i];nums[i]=nums[j];nums[j]=t;} // cyclic swap to put nums[i] at its correct position
        for(int i=0;i<n;i++)if(nums[i]!=i+1)return i+1;return n+1;} // scan for first index where value != index+1
        // Original main method from the snippet (kept verbatim)
          public static void main(String[] args){System.out.println(new Solution().firstMissingPositive(new int[]{3,4,-1,1}));}
    }

    // Main entry point demonstrating the solution with multiple test cases
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test case 1: Example from the snippet
        int[] test1 = {3, 4, -1, 1};
        System.out.println("Test 1: " + sol.firstMissingPositive(test1)); // Expected: 2
        // Test case 2: Already sequential positive integers
        int[] test2 = {1, 2, 3};
        System.out.println("Test 2: " + sol.firstMissingPositive(test2)); // Expected: 4
        // Test case 3: Missing at the start
        int[] test3 = {2, 3, 4};
        System.out.println("Test 3: " + sol.firstMissingPositive(test3)); // Expected: 1
        // Test case 4: With duplicates and non-positive numbers
        int[] test4 = {1, 1, 0, -1, 2};
        System.out.println("Test 4: " + sol.firstMissingPositive(test4)); // Expected: 3
        // Test case 5: Empty array
        int[] test5 = {};
        System.out.println("Test 5: " + sol.firstMissingPositive(test5)); // Expected: 1
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Array + head + size; rear = (head+size-1)%k.

Easy Algorithm

1. enQueue if not full
2. deQueue advance head
3. Front/Rear by head/size

Code (Java)

// Import Java utility classes like List, ArrayList, Arrays.
import java.util.*;

// Main class containing the entry point for the program.
public class Main {
    // Main method: sets up test operations and runs the circular queue simulation.
    public static void main(String[] args) {
        // Define a list of operations to simulate the circular queue API.
        List<List<Object>> ops = Arrays.asList(
            // Create a circular queue with capacity 3.
            Arrays.asList("MyCircularQueue", 3),
            // Enqueue value 1.
            Arrays.asList("enQueue", 1),
            // Enqueue value 2.
            Arrays.asList("enQueue", 2),
            // Enqueue value 3 (queue becomes full).
            Arrays.asList("enQueue", 3),
            // Attempt to enqueue 4 (should fail, queue is full).
            Arrays.asList("enQueue", 4),
            // Get the rear element.
            Arrays.asList("Rear"),
            // Check if queue is full.
            Arrays.asList("isFull"),
            // Dequeue an element.
            Arrays.asList("deQueue"),
            // Enqueue 4 again (should succeed now).
            Arrays.asList("enQueue", 4),
            // Get the rear element again.
            Arrays.asList("Rear")
        );
        // Instantiate the Solution class that contains the queue logic.
        Solution sol = new Solution();
        // Execute the sequence of operations and collect results.
        List<Object> result = sol.runCircularQueue(ops);
        // Print the list of results to console.
        System.out.println(result);
    }
}

// Solution class containing the circular queue implementation and runner.
class Solution {
// Inner class MyCircularQueue: array-backed circular queue with head index and size.
static class MyCircularQueue{int[] a;int head,size;
// Constructor allocates the internal array of given capacity k.
MyCircularQueue(int k){a=new int[k];}
// enQueue: inserts value at tail position (head+size)%capacity; returns false if full.
boolean enQueue(int v){if(isFull())return false;a[(head+size)%a.length]=v;size++;return true;}
// deQueue: advances head index modulo capacity and decrements size; returns false if empty.
boolean deQueue(){if(isEmpty())return false;head=(head+1)%a.length;size--;return true;}
// Front returns element at head; Rear returns element at tail (head+size-1)%capacity; both return -1 if empty.
int Front(){return isEmpty()?-1:a[head];} int Rear(){return isEmpty()?-1:a[(head+size-1)%a.length];}
// isEmpty checks size==0; isFull checks size==capacity.
boolean isEmpty(){return size==0;} boolean isFull(){return size==a.length;}}
// runCircularQueue: processes a list of operation calls and returns a list of results.
public List<Object> runCircularQueue(List<List<Object>> ops){MyCircularQueue q=null;List<Object> out=new ArrayList<>();
// Loop over each operation; on "MyCircularQueue" create new queue and add null to output.
for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("MyCircularQueue")){q=new MyCircularQueue((Integer)op.get(1));out.add(null);}
// Handle enQueue and deQueue operations, appending their boolean results.
else if(m.equals("enQueue"))out.add(q.enQueue((Integer)op.get(1)));else if(m.equals("deQueue"))out.add(q.deQueue());
// Handle Front and Rear queries, appending the returned integer values.
else if(m.equals("Front"))out.add(q.Front());else if(m.equals("Rear"))out.add(q.Rear());
// Handle isEmpty and isFull queries, appending boolean results; return the output list.
else if(m.equals("isEmpty"))out.add(q.isEmpty());else out.add(q.isFull());}return out;}
  // Unused main method inside Solution (likely a leftover).
  public static void main(String[] args){System.out.println("ok");}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Map key→list of (ts,val); binary search on get.

Easy Algorithm

1. append on set (ts increasing)
2. bisect right for ≤ts
3. return value or empty

Code (Java)

// Import Java utility classes for collections like List, ArrayList, Arrays.
import java.util.*;

// Define the Main class containing the program entry point.
public class Main {
    // Main method that builds sample operations and executes the TimeMap simulation.
    public static void main(String[] args) {
        // build sample ops
        // Create a list of operations where each operation is a list of objects (method name + args).
        List<List<Object>> ops = Arrays.asList(
            // First operation: instantiate a new TimeMap.
            Arrays.asList("TimeMap"),
            // Second operation: set key 'foo' to value 'bar' at timestamp 1.
            Arrays.asList("set", "foo", "bar", 1),
            // Third operation: get value for key 'foo' at timestamp 1.
            Arrays.asList("get", "foo", 1),
            // Fourth operation: get value for key 'foo' at timestamp 3.
            Arrays.asList("get", "foo", 3),
            // Fifth operation: set key 'foo' to value 'bar2' at timestamp 4.
            Arrays.asList("set", "foo", "bar2", 4),
            // Sixth operation: get value for key 'foo' at timestamp 4.
            Arrays.asList("get", "foo", 4),
            // Seventh operation: get value for key 'foo' at timestamp 5.
            Arrays.asList("get", "foo", 5)
        );
        // Create an instance of Solution to run the TimeMap operations.
        Solution sol = new Solution();
        // Execute the operations and collect results in a list.
        List<Object> result = sol.runTimeMap(ops);
        // Print the results to standard output.
        System.out.println(result);
    }
}

// snippet verbatim below
// Define the Solution class containing TimeMap implementation and runner.
class Solution {
// Define TimeMap inner class with a map storing key to list of int arrays (unused field).
static class TimeMap{Map<String,List<int[]>> m=new HashMap<>(); // store idx+string separately
// Two maps: vals stores key to list of string values, ts stores key to list of timestamps.
Map<String,List<String>> vals=new HashMap<>();Map<String,List<Integer>> ts=new HashMap<>();
// Set method: appends timestamp to ts map and value to vals map for the given key.
void set(String k,String v,int t){ts.computeIfAbsent(k,x->new ArrayList<>()).add(t);vals.computeIfAbsent(k,x->new ArrayList<>()).add(v);}
// Get method: binary searches timestamps list for largest timestamp <= target, returns corresponding value or empty string.
String get(String k,int t){List<Integer> a=ts.get(k);if(a==null)return "";int lo=0,hi=a.size()-1,ans=-1;while(lo<=hi){int mid=(lo+hi)/2;if(a.get(mid)<=t){ans=mid;lo=mid+1;}else hi=mid-1;}return ans<0?"":vals.get(k).get(ans);}}
// runTimeMap method: processes a list of operations, maintains TimeMap instance, returns list of results.
public List<Object> runTimeMap(List<List<Object>> ops){TimeMap tm=null;List<Object> out=new ArrayList<>();
// Iterate through operations; on 'TimeMap' create new instance and add null to output.
for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("TimeMap")){tm=new TimeMap();out.add(null);}
// On 'set' operation, call set with key, value, timestamp and add null to output.
else if(m.equals("set")){tm.set((String)op.get(1),(String)op.get(2),(Integer)op.get(3));out.add(null);}
// On 'get' operation, call get with key and timestamp, add returned value to output.
else out.add(tm.get((String)op.get(1),(Integer)op.get(2)));}return out;}
  // Static main method for standalone testing, prints 'ok'.
  public static void main(String[] args){System.out.println("ok");}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Queue of timestamps; evict < t-299 on getHits.

Easy Algorithm

1. enqueue on hit
2. evict old on query
3. return size

Code (Java)

import java.util.*;

public class Main {
    // Main class to demonstrate the HitCounter solution
    // Solution is nested as a static class so the single file stays valid on older Java versions
    static class Solution {
        // HitCounter uses a deque to store timestamps of hits
        static class HitCounter{Deque<Integer> q=new ArrayDeque<>(); // stores hit timestamps
        void hit(int t){q.addLast(t);} // record a hit at time t
        int getHits(int t){while(!q.isEmpty()&&q.peekFirst()<=t-300)q.pollFirst();return q.size();}} // remove hits older than 300 seconds, return count
        public List<Object> runHitCounter(List<List<Object>> ops){HitCounter h=null;List<Object> out=new ArrayList<>(); // process operations
        for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("HitCounter")){h=new HitCounter();out.add(null);} // initialize HitCounter
        else if(m.equals("hit")){h.hit((Integer)op.get(1));out.add(null);}else out.add(h.getHits((Integer)op.get(1)));}return out;} // handle hit or getHits
          public static void main(String[] args){System.out.println("ok");} // snippet's own main (not used)
    }

    // Main entry point
    public static void main(String[] args) {
        // Create an instance of Solution
        Solution sol = new Solution();
        // Define a sequence of operations to test HitCounter
        List<List<Object>> ops = new ArrayList<>();
        ops.add(Arrays.asList("HitCounter"));
        ops.add(Arrays.asList("hit", 1));
        ops.add(Arrays.asList("hit", 2));
        ops.add(Arrays.asList("hit", 3));
        ops.add(Arrays.asList("getHits", 4));
        ops.add(Arrays.asList("hit", 300));
        ops.add(Arrays.asList("getHits", 300));
        ops.add(Arrays.asList("getHits", 301));
        // Run the operations and print results
        List<Object> result = sol.runHitCounter(ops);
        System.out.println("Result: " + result);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Stack of (price,span); pop ≤ today's price accumulating spans.

Easy Algorithm

1. span=1
2. while top.price<=price: span+=top.span pop
3. push (price,span)

Code (Java)

import java.util.*;

public class Main {
    // Solution is nested as a static class so the single file stays valid on older Java versions
    static class Solution {
static class StockSpanner{Deque<int[]> st=new ArrayDeque<>(); // monotonic decreasing stack of (price, span)
int next(int price){int span=1;while(!st.isEmpty()&&st.peek()[0]<=price)span+=st.pop()[1];st.push(new int[]{price,span});return span;}} // compute span for price
public List<Object> runStockSpanner(List<List<Object>> ops){StockSpanner s=null;List<Object> out=new ArrayList<>(); // process operations
for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("StockSpanner")){s=new StockSpanner();out.add(null);}else out.add(s.next((Integer)op.get(1)));}return out;} // iterate ops
  public static void main(String[] args){System.out.println("ok");} // demo main in Solution
    }

    public static void main(String[] args) {
        // Create Solution instance
        Solution sol = new Solution();
        // Prepare sample operations: constructor then a series of next calls
        List<List<Object>> ops = new ArrayList<>();
        ops.add(List.of("StockSpanner"));
        ops.add(List.of("next", 100));
        ops.add(List.of("next", 80));
        ops.add(List.of("next", 60));
        ops.add(List.of("next", 70));
        ops.add(List.of("next", 60));
        ops.add(List.of("next", 75));
        ops.add(List.of("next", 85));
        // Run the stock spanner simulation
        List<Object> result = sol.runStockSpanner(ops);
        // Print the resulting spans (null for constructor, then spans)
        System.out.println("Stock spans: " + result);
    }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Mono decreasing stack on nums2 → map next greater; probe nums1.

Easy Algorithm

1. scan nums2 right/left with stack
2. map value→next greater
3. lookup nums1

Code (Java)

import java.util.*;

// Main class to demonstrate the Solution
public class Main {
    public static void main(String[] args) {
        // Create an instance of Solution
        Solution sol = new Solution();
        // Test case from the snippet
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        int[] result = sol.nextGreaterElement(nums1, nums2);
        // Print the result
        System.out.println("Result: " + Arrays.toString(result));
        // Also run the original main from Solution for verification
        Solution.main(args);
    }
}

// Solution class containing the nextGreaterElement algorithm
class Solution {
    // Method to compute next greater elements for nums1 based on nums2
    public int[] nextGreaterElement(int[] nums1,int[] nums2){Map<Integer,Integer> next=new HashMap<>();Deque<Integer> st=new ArrayDeque<>(); // initialize map and stack
    // Iterate through nums2, maintaining a decreasing stack to find next greater
    for(int x:nums2){while(!st.isEmpty()&&st.peek()<x)next.put(st.pop(),x);st.push(x);} // process each element
    // Build result array by looking up each nums1 element in the map
    int[] ans=new int[nums1.length];for(int i=0;i<nums1.length;i++)ans[i]=next.getOrDefault(nums1[i],-1);return ans;} // fill ans and return
    // Original main method from the snippet for quick test
      public static void main(String[] args){System.out.println(Arrays.toString(new Solution().nextGreaterElement(new int[]{4,1,2},new int[]{1,3,4,2})));} // print test result
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Count map; min-heap of size k with custom comparator (freq, then reverse alpha).

Easy Algorithm

1. count words
2. heap keep top k
3. extract sorted

Code (Java)

import java.util.*;

// Main class to run the solution
public class Main {
    public static void main(String[] args) {
        // Create Solution instance and call topKFrequent with sample input
        Solution sol = new Solution();
        List<String> result = sol.topKFrequent(new String[]{"i","love","leetcode","i","love","coding"}, 2);
        // Print the result
        System.out.println(result);
    }
}

// Solution class implementing top K frequent words algorithm
class Solution {
// Count word frequencies using HashMap
public List<String> topKFrequent(String[] words,int k){Map<String,Integer> cnt=new HashMap<>();for(String w:words)cnt.merge(w,1,Integer::sum);
// Create min-heap with custom comparator: first by frequency (ascending), then by reverse lexicographical order
PriorityQueue<String> pq=new PriorityQueue<>((a,b)->{int c=cnt.get(a)-cnt.get(b);return c!=0?c:b.compareTo(a);});
// Add all words to heap, keeping only top k by polling when size exceeds k
for(String w:cnt.keySet()){pq.offer(w);if(pq.size()>k)pq.poll();}List<String> res=new ArrayList<>();while(!pq.isEmpty())res.add(pq.poll());Collections.reverse(res);return res;}
// Original main method from snippet (kept for reference)
  public static void main(String[] args){System.out.println(new Solution().topKFrequent(new String[]{"i","love","leetcode","i","love","coding"},2));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Sort by start; if intervals[i].start < intervals[i-1].end → false.

Easy Algorithm

1. sort by start
2. check adjacent overlap

Code (Java)

import java.util.*;

/**
 * Main class to demonstrate the meeting rooms solution.
 */
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution(); // create instance
        // Test case 1: overlapping meetings
        int[][] intervals1 = {{0,30},{5,10},{15,20}};
        System.out.println("Test 1 (overlap): " + sol.canAttendMeetings(intervals1)); // expected false
        // Test case 2: non-overlapping meetings
        int[][] intervals2 = {{7,10},{2,4}};
        System.out.println("Test 2 (no overlap): " + sol.canAttendMeetings(intervals2)); // expected true
        // Test case 3: empty intervals
        int[][] intervals3 = {};
        System.out.println("Test 3 (empty): " + sol.canAttendMeetings(intervals3)); // expected true
        // Test case 4: single meeting
        int[][] intervals4 = {{5,10}};
        System.out.println("Test 4 (single): " + sol.canAttendMeetings(intervals4)); // expected true
    }
}

/**
 * Solution class that checks if a person can attend all meetings without overlap.
 */
class Solution {
public boolean canAttendMeetings(int[][] intervals){Arrays.sort(intervals,Comparator.comparingInt(a->a[0])); // sort intervals by start time
for(int i=1;i<intervals.length;i++)if(intervals[i][0]<intervals[i-1][1])return false;return true;} // check adjacent intervals for overlap
  public static void main(String[] args){System.out.println(new Solution().canAttendMeetings(new int[][]{{0,30},{5,10},{15,20}}));} // original main for demonstration
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Array for values; map val→index; swap-remove last on delete.

Easy Algorithm

1. insert if absent append
2. remove swap with last
3. getRandom index

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Build a sequence of operations to exercise RandomizedSet
        List<List<Object>> ops = new ArrayList<>();
        ops.add(Arrays.asList("RandomizedSet"));           // constructor call
        ops.add(Arrays.asList("insert", 10));              // insert 10 -> true
        ops.add(Arrays.asList("insert", 20));              // insert 20 -> true
        ops.add(Arrays.asList("insert", 10));              // insert duplicate 10 -> false
        ops.add(Arrays.asList("remove", 20));              // remove 20 -> true
        ops.add(Arrays.asList("remove", 30));              // remove absent 30 -> false
        ops.add(Arrays.asList("getRandom"));               // random from {10}
        ops.add(Arrays.asList("getRandom"));               // random from {10}
        ops.add(Arrays.asList("getRandom"));               // random from {10}
        
        List<Object> results = sol.runRandomizedSet(ops);
        
        // Print each result so the reader sees the output
        for (Object result : results) {
            System.out.println(result);
        }
    }
}

// Solution class containing RandomizedSet (O(1) insert/remove/getRandom) and test runner
class Solution {
    // RandomizedSet: ArrayList stores values, HashMap maps value->index, fixed-seed Random for determinism
    static class RandomizedSet{List<Integer> a=new ArrayList<>();Map<Integer,Integer> idx=new HashMap<>();Random r=new Random(0);
    // insert: if value exists return false; else append to list, record index, return true
    boolean insert(int v){if(idx.containsKey(v))return false;idx.put(v,a.size());a.add(v);return true;}
    // remove: if value absent return false; else swap with last, pop last, update map, return true
    boolean remove(int v){if(!idx.containsKey(v))return false;int i=idx.get(v),last=a.get(a.size()-1);a.set(i,last);idx.put(last,i);a.remove(a.size()-1);idx.remove(v);return true;}
    // getRandom: pick random index from list and return that value
    int getRandom(){return a.get(r.nextInt(a.size()));}}
    // runRandomizedSet: interprets a list of operations, returns list of results (null for constructor)
    public List<Object> runRandomizedSet(List<List<Object>> ops){RandomizedSet s=null;List<Object> out=new ArrayList<>();
    for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("RandomizedSet")){s=new RandomizedSet();out.add(null);}
    else if(m.equals("insert"))out.add(s.insert((Integer)op.get(1)));else if(m.equals("remove"))out.add(s.remove((Integer)op.get(1)));
    else out.add(s.getRandom());}return out;}
    // Original main from snippet (not used when running Main)
    public static void main(String[] args){System.out.println("ok");}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Push numbers; on op pop2 apply push.

Easy Algorithm

1. if number push
2. else pop b,a apply a op b

Code (Java)

import java.util.*;

// Main class demonstrating the RPN evaluator
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        // Test 1: (2 + 1) * 3 = 9
        String[] tokens1 = {"2", "1", "+", "3", "*"};
        System.out.println("Test 1: " + sol.evalRPN(tokens1));
        // Test 2: 4 + (13 * 5) = 69
        String[] tokens2 = {"4", "13", "5", "*", "+"};
        System.out.println("Test 2: " + sol.evalRPN(tokens2));
        // Test 3: (10 - 6) * 2 = 8
        String[] tokens3 = {"10", "6", "-", "2", "*"};
        System.out.println("Test 3: " + sol.evalRPN(tokens3));
    }
}

// Solution class implementing Reverse Polish Notation evaluation
class Solution {
    // Evaluates RPN expression using a stack
    public int evalRPN(String[] tokens){Deque<Integer> st=new ArrayDeque<>();
    // Iterate through each token
    for(String t:tokens){if(t.equals("+")||t.equals("-")||t.equals("*")||t.equals("/")){int b=st.pop(),a=st.pop();
    // Apply operator: pop two operands, compute, push result
    if(t.equals("+"))st.push(a+b);else if(t.equals("-"))st.push(a-b);else if(t.equals("*"))st.push(a*b);else st.push(a/b);}else st.push(Integer.parseInt(t));}
    // Final result is the only element left on stack
    return st.pop();}
    // Original main method from snippet (kept as-is)
      public static void main(String[] args){System.out.println(new Solution().evalRPN(new String[]{"2","1","+","3","*"}));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Scan numbers; on * / apply immediately to last; on + - push signed term; sum stack.

Easy Algorithm

1. parse number
2. on op flush previous
3. * / update last; + - push

Code (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        // Test the calculator with various expressions
        System.out.println("3+2*2 = " + solution.calculate("3+2*2"));
        System.out.println(" 3/2 = " + solution.calculate(" 3/2 "));
        System.out.println("3+5 / 2 = " + solution.calculate("3+5 / 2"));
        System.out.println("1+2*3-4/2 = " + solution.calculate("1+2*3-4/2"));
    }
}

class Solution {
    // Evaluates a basic arithmetic expression containing +, -, *, / and spaces
    public int calculate(String s){Deque<Integer> st=new ArrayDeque<>();int num=0;char sign='+';
    // Iterate through each character of the input string
    for(int i=0;i<s.length();i++){char c=s.charAt(i);if(Character.isDigit(c))num=num*10+c-'0';
    // When operator or end of string is reached, process the accumulated number with previous sign
    if((!Character.isDigit(c)&&c!=' ')||i==s.length()-1){if(sign=='+')st.push(num);else if(sign=='-')st.push(-num);
    // For * and /, immediately apply to the last value in stack (higher precedence)
    else if(sign=='*')st.push(st.pop()*num);else st.push(st.pop()/num);sign=c;num=0;}}
    // Sum all values in stack to produce final result
    int sum=0;for(int x:st)sum+=x;return sum;}
    // Demo main method included in original snippet
      public static void main(String[] args){System.out.println(new Solution().calculate("3+2*2"));}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

HashMap to nodes; doubly linked list for recency; move-to-front on access.

Easy Algorithm

1. get: move front or -1
2. put: update/move or insert
3. evict tail if over cap

Code (Java)

// Import standard Java utilities including List, Map, HashMap, Arrays, ArrayList.
import java.util.*;

/** Main class: runs a short LRUCache scenario through Solution.runLRU and prints the results. */
public class Main {
    public static void main(String[] args) {
        // Capacity 2: put(1,1), put(2,2), get(1) -> 1, put(3,3) evicts key 2, get(2) -> -1
        List<List<Object>> ops = Arrays.asList(
            Arrays.asList("LRUCache", 2),
            Arrays.asList("put", 1, 1),
            Arrays.asList("put", 2, 2),
            Arrays.asList("get", 1),
            Arrays.asList("put", 3, 3),
            Arrays.asList("get", 2));
        System.out.println(new Solution().runLRU(ops)); // [null, null, null, 1, null, -1]
    }
}

// Solution class containing the LRUCache implementation and a driver to execute operations.
class Solution {
// Inner class LRUCache implements a Least Recently Used cache with O(1) get and put.
static class LRUCache{
// Static nested Node class for doubly linked list; stores key, value, prev, next pointers.
static class N{int k,v;N p,n;N(int k,int v){this.k=k;this.v=v;}}
// Cache fields: capacity, hashmap for O(1) key lookup, dummy head/tail nodes to simplify list ops.
int cap;Map<Integer,N> m=new HashMap<>();N head=new N(0,0),tail=new N(0,0);
// Constructor sets capacity and links dummy head and tail to each other (empty list).
LRUCache(int c){cap=c;head.n=tail;tail.p=head;}
// add inserts a node right after head, making it the most recently used.
void add(N x){x.n=head.n;x.p=head;head.n.p=x;head.n=x;}
// rem unlinks a node from the doubly linked list.
void rem(N x){x.p.n=x.n;x.n.p=x.p;}
// get returns value for key if present, moves accessed node to front (MRU), else -1.
int get(int k){N x=m.get(k);if(x==null)return -1;rem(x);add(x);return x.v;}
// put updates existing key or inserts new node; evicts LRU (tail.prev) when over capacity.
void put(int k,int v){N x=m.get(k);if(x!=null){x.v=v;rem(x);add(x);return;}x=new N(k,v);m.put(k,x);add(x);if(m.size()>cap){N lru=tail.p;rem(lru);m.remove(lru.k);}}}
// runLRU interprets a list of operation lists, executes them on an LRUCache, collects outputs.
public List<Object> runLRU(List<List<Object>> ops){LRUCache c=null;List<Object> out=new ArrayList<>();
// Iterates operations; on "LRUCache" creates new cache with given capacity, records null.
for(List<Object> op:ops){String m=(String)op.get(0);if(m.equals("LRUCache")){c=new LRUCache((Integer)op.get(1));out.add(null);}
// On "put" calls put and records null; on "get" calls get and records returned value.
else if(m.equals("put")){c.put((Integer)op.get(1),(Integer)op.get(2));out.add(null);}else out.add(c.get((Integer)op.get(1)));}return out;}
  public static void main(String[] args){System.out.println("ok");}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

Max-heap lo + min-heap hi; rebalance sizes; median from tops.

Easy Algorithm

1. push to lo or hi by value
2. rebalance |lo-hi|≤1
3. median mid or avg

Code (Java)

// Import Java utility classes for collections and priority queues.
import java.util.*;

/** Main class: runs a short MedianFinder scenario through Solution.runMedianFinder and prints the results. */
public class Main {
    public static void main(String[] args) {
        // addNum(1), addNum(2) -> median 1.5; addNum(3) -> median 2.0
        List<List<Object>> ops = Arrays.asList(
            Arrays.asList("MedianFinder"),
            Arrays.asList("addNum", 1),
            Arrays.asList("addNum", 2),
            Arrays.asList("findMedian"),
            Arrays.asList("addNum", 3),
            Arrays.asList("findMedian"));
        System.out.println(new Solution().runMedianFinder(ops)); // [null, null, null, 1.5, null, 2.0]
    }
}

// Solution class definition.
class Solution {
// MedianFinder inner class using two heaps: 'lo' (max-heap) stores the lower half, 'hi' (min-heap) stores the upper half.
static class MedianFinder{PriorityQueue<Integer> lo=new PriorityQueue<>(Collections.reverseOrder());PriorityQueue<Integer> hi=new PriorityQueue<>();
// addNum inserts a number into the appropriate heap then rebalances so sizes differ by at most one.
void addNum(int n){if(lo.isEmpty()||n<=lo.peek())lo.offer(n);else hi.offer(n);if(lo.size()>hi.size()+1)hi.offer(lo.poll());else if(hi.size()>lo.size())lo.offer(hi.poll());}
// findMedian returns the top of the larger heap, or the average of both tops when sizes are equal.
double findMedian(){if(lo.size()>hi.size())return lo.peek();return (lo.peek()+hi.peek())/2.0;}}
// runMedianFinder executes a list of operations (constructor, addNum, findMedian) and collects outputs.
public List<Object> runMedianFinder(List<List<Object>> ops){MedianFinder m=null;List<Object> out=new ArrayList<>();
// Iterates over operations; on 'MedianFinder' creates a new instance and records null output.
for(List<Object> op:ops){String s=(String)op.get(0);if(s.equals("MedianFinder")){m=new MedianFinder();out.add(null);}
// On 'addNum' delegates to MedianFinder and records null; otherwise calls findMedian and records the median.
else if(s.equals("addNum")){m.addNum((Integer)op.get(1));out.add(null);}else out.add(m.findMedian());}return out;}
  // Secondary main method (unused in this test) that simply prints 'ok'.
  public static void main(String[] args){System.out.println("ok");}
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

See lab tests / Run main.

Also asked: Amazon, Target

Approach

At each travel day index, choose buy 1/7/30 and jump to the next uncovered day; memoize on index.

Easy Algorithm

1. If i ≥ n return 0
2. Option 1-day: costs[0] + dp(i+1)
3. Find first day ≥ days[i]+7 / +30 for other options
4. Return min; memoize

Code (Java)

import java.util.*;

// Main class to execute the solution and demonstrate its usage
public class Main {
    public static void main(String[] args) {
        // Create an instance of the Solution class
        Solution solution = new Solution();
        
        // Test case 1: Example from the problem description
        int[] days1 = {1, 4, 6, 7, 8, 20};
        int[] costs1 = {2, 7, 15};
        int result1 = solution.mincostTickets(days1, costs1);
        System.out.println("Test case 1 - Minimum cost: " + result1);
        
        // Test case 2: Additional test with more travel days
        int[] days2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31};
        int[] costs2 = {2, 7, 15};
        int result2 = solution.mincostTickets(days2, costs2);
        System.out.println("Test case 2 - Minimum cost: " + result2);
    }
}

// Solution class implementing the minimum cost for tickets algorithm using DP with memoization
class Solution {
  // Public method to calculate minimum cost for tickets given travel days and pass costs
  public int mincostTickets(int[] days, int[] costs) {
    int[] memo = new int[days.length];           // Memoization array initialized to -1
    Arrays.fill(memo, -1);                       // Fill memo with -1 to indicate uncomputed states
    return dp(days, costs, 0, memo);             // Start DP from day index 0
  }
  // Recursive DP helper with memoization: returns min cost from index i onwards
  int dp(int[] days, int[] costs, int i, int[] memo) {
    if (i >= days.length) return 0;              // Base case: no more travel days, cost is 0
    if (memo[i] >= 0) return memo[i];            // Return cached result if already computed
    int best = costs[0] + dp(days, costs, i + 1, memo); // Option 1: buy 1-day pass for days[i]
    int j = i;                                   // Find first day not covered by 7-day pass
    while (j < days.length && days[j] < days[i] + 7) j++;
    best = Math.min(best, costs[1] + dp(days, costs, j, memo)); // Option 2: 7-day pass
    j = i;                                       // Find first day not covered by 30-day pass
    while (j < days.length && days[j] < days[i] + 30) j++;
    best = Math.min(best, costs[2] + dp(days, costs, j, memo)); // Option 3: 30-day pass
    return memo[i] = best;                       // Cache and return minimum cost
  }
  // Original main method from the snippet for standalone testing
  public static void main(String[] args) {
    System.out.println(new Solution().mincostTickets(new int[]{1,4,6,7,8,20}, new int[]{2,7,15}));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

Sample [1,4,6,7,8,20]/[2,7,15] → 11. See lab tests.

Also asked: Job Prep DP · Amazon, Target

Approach

Include/exclude recursion on (i, remainingWeight); memoize — core DP definition from Job Prep.

Easy Algorithm

1. Base: i==n or w==0 → 0
2. Skip = dp(i+1,w)
3. Take if weight fits
4. Memoize max

Code (Java)

import java.util.*; // Import utilities for Arrays.fill
/**
 * Main entry point that demonstrates the 0/1 Knapsack solution.
 * Creates a Solution instance and runs a sample test case.
 */
public class Main {
    public static void main(String[] args) {
        // Test the Solution class with sample data
        Solution sol = new Solution();
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;
        int result = sol.knapsack(weights, values, capacity);
        System.out.println("Max value: " + result);
    }
}
/**
 * Solution for 0/1 Knapsack problem using top-down DP with memoization.
 * Each item can be taken at most once to maximize value under weight capacity.
 */
class Solution { // Solution class definition
  public int knapsack(int[] weights, int[] values, int capacity) { // Knapsack entry method
    int n = weights.length; // Number of items
    int[][] memo = new int[n][capacity + 1]; // Memoization table: [item index][remaining weight]
    for (int[] row : memo) Arrays.fill(row, -1); // Initialize memo with -1 (uncomputed)
    return dfs(0, capacity, weights, values, memo); // Start recursion from first item with full capacity
  } // End knapsack
  int dfs(int i, int w, int[] wt, int[] val, int[][] memo) { // Recursive DFS with memo
    if (i == wt.length || w == 0) return 0; // Base case: no items left or no capacity
    if (memo[i][w] >= 0) return memo[i][w]; // Return cached result if available
    int best = dfs(i + 1, w, wt, val, memo); // Option 1: skip current item
    if (wt[i] <= w) best = Math.max(best, val[i] + dfs(i + 1, w - wt[i], wt, val, memo)); // Option 2: take current item if it fits
    return memo[i][w] = best; // Cache and return best value
  } // End dfs
  public static void main(String[] args) { // Original test main in Solution
    System.out.println(new Solution().knapsack(new int[]{1,2,3}, new int[]{6,10,12}, 5)); // Run sample test
  } // End Solution.main
} // End Solution class

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

wt[1,2,3] val[6,10,12] W=5 → 22. See lab tests.

Also asked: Job Prep DP · Amazon, Target

Approach

One-pass state machine: b1/s1/b2/s2.

Easy Algorithm

1. Init buys to −∞, sells to 0
2. Update first buy/sell
3. Update second buy/sell
4. Return s2

Code (Java)

import java.util.*;

/** Main class: runs the two-transaction stock profit example and prints the result. */
public class Main {
    public static void main(String[] args) {
        // Prices 3,3,5,0,0,3,1,4: buy at 0 sell at 3, then buy at 1 sell at 4 -> profit 3 + 3 = 6
        System.out.println(new Solution().maxProfit(new int[]{3,3,5,0,0,3,1,4})); // 6
    }
}

/** Solution class: best profit with at most two buy/sell transactions. */
class Solution {
  // Method to calculate maximum profit with at most two transactions
  public int maxProfit(int[] prices) {
    // Initialize four state variables: b1/b2 track best buy prices, s1/s2 track best sell profits
    int b1 = Integer.MIN_VALUE / 4, b2 = Integer.MIN_VALUE / 4, s1 = 0, s2 = 0;
    // Iterate through each day's stock price
    for (int p : prices) {
      // Update first buy: either keep previous best or buy today (negative price)
      b1 = Math.max(b1, -p);
      // Update first sell: either keep previous best or sell today using best first buy
      s1 = Math.max(s1, b1 + p);
      // Update second buy: either keep previous best or buy today using profit from first sell
      b2 = Math.max(b2, s1 - p);
      // Update second sell: either keep previous best or sell today using best second buy
      s2 = Math.max(s2, b2 + p);
    }
    // Return maximum profit after at most two transactions
    return s2;
  }
  // Second main method for standalone testing of Solution class
  public static void main(String[] args) {
    // Run the same test case and print result
    System.out.println(new Solution().maxProfit(new int[]{3,3,5,0,0,3,1,4}));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[3,3,5,0,0,3,1,4] → 6. See lab tests.

Also asked: Job Prep DP · Amazon, Target

Approach

In-place row DP: each color adds min of other two from previous house.

Easy Algorithm

1. For i=1..n-1 update each color
2. Add min of other colors from i-1
3. Return min of last row

Code (Java)

import java.util.*;

// Main class: entry point that demonstrates the Paint House DP solution
public class Main {
    public static void main(String[] args) {
        // Create an instance of the Solution class
        Solution solver = new Solution();
        // Example costs matrix: 3 houses, 3 colors each
        int[][] costs = {
            {17, 2, 17},
            {16, 16, 5},
            {14, 3, 19}
        };
        // Compute and print minimum painting cost
        int result = solver.minCost(costs);
        System.out.println("Minimum cost: " + result);
        // Additional test case from the snippet's own main
        System.out.println("Snippet's test result: " + solver.minCost(new int[][]{{17,2,17},{16,16,5},{14,3,19}}));
    }
}

// Solution class: contains the minCost method for Paint House problem (in-place DP)
class Solution {
  public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0) return 0; // Handle empty input
    int n = costs.length; // Number of houses
    for (int i = 1; i < n; i++) { // Iterate from second house
      costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]); // Red: add min of previous Blue/Green
      costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]); // Blue: add min of previous Red/Green
      costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]); // Green: add min of previous Red/Blue
    }
    return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2])); // Min of last house
  }
  public static void main(String[] args) {
    System.out.println(new Solution().minCost(new int[][]{{17,2,17},{16,16,5},{14,3,19}}));
  }
}

Java shown for learning; Interactive Lab below runs a JS twin (same tests / custom / main).

Walkthrough

[[17,2,17],[16,16,5],[14,3,19]] → 10. See lab tests.

Also asked: Job Prep DP · Amazon, Target

Model / APIs

- Wallet, LedgerEntry, Hold, Transfer, IdempotencyKey

- POST /wallets/{id}/credit, /debit, /transfer

Concurrency

Optimistic version + unique idempotency; outbox for statements

Pods & Scaling

3–6 pods; HPA on p99 debit latency & CPU; Redis for idempotency cache

Metrics / Deploy

`debit_p99_ms, transfer_error_rate, ledger_lag_seconds, pool_saturation` — alert on SLO burn (p99, error rate, saturation).

Rolling with expand/contract schema; feature-flag new FX path; rollback by disabling write path

Model / APIs

- SKU, Reservation, Warehouse, AllocationPolicy

- POST /reserve, /confirm, /release

Concurrency

Conditional stock decrement; outbox events

Pods & Scaling

Pods colocated per region/warehouse shard; HPA on reserve QPS

Metrics / Deploy

`reserve_success_rate, stock_negative_violations, expire_lag, db_cpu` — alert on SLO burn (p99, error rate, saturation).

Blue-green for allocation policy; dual-write reservation table; instant flag rollback

Model / APIs

- Coupon, Rule, Redemption, Budget

- POST /quote, /redeem, GET /coupons/{code}

Concurrency

Strategy rules; budget CAS; idempotent redeem

Pods & Scaling

Stateless pods + Redis budget counters; HPA on quote QPS

Metrics / Deploy

`quote_p99, redeem_conflict_rate, budget_exhaustion, cache_hit` — alert on SLO burn (p99, error rate, saturation).

Rolling rule pack via config; canary percent; rollback config revision

Model / APIs

- Trie / completion index, Suggestion, Ranker

- GET /suggest?q=

Concurrency

Trie or ES completion; cache hot prefixes

Pods & Scaling

Read-heavy pods; CDN/edge cache; HPA on RPS

Metrics / Deploy

`suggest_p99, empty_rate, index_lag, cache_hit` — alert on SLO burn (p99, error rate, saturation).

Offline rebuild; blue-green index alias swap; rollback alias

Model / APIs

- AuditEvent, Sink, QueryAPI

- POST /events, GET /events?actor=

Concurrency

Hash chain optional; WORM storage

Pods & Scaling

Ingest pods + async object store; HPA on ingest lag

Metrics / Deploy

`ingest_p99, drop_rate, query_p99, disk_saturation` — alert on SLO burn (p99, error rate, saturation).

Schema-additive only; dual-write during migrate; rollback readers

Model / APIs

- Tenant, ConfigKey, Overlay, Version

- GET/PUT /tenants/{id}/config/{key}

Concurrency

Copy-on-write versions; etag

Pods & Scaling

HA pods + strongly consistent store

Metrics / Deploy

`get_p99, stale_read_rate, publish_fail, watch_lag` — alert on SLO burn (p99, error rate, saturation).

Expand/contract keys; flag new schema; rollback version pin

Model / APIs

- Job, Schedule, Run, Lease

- POST /jobs, POST /runs/{id}/heartbeat

Concurrency

Leader lease + claim CAS

Pods & Scaling

Scheduler pods + worker fleets; HPA workers on queue depth

Metrics / Deploy

`claim_lag, duplicate_runs, fail_rate, lease_expire` — alert on SLO burn (p99, error rate, saturation).

Rolling workers first; additive job defs; pause schedules for rollback

Model / APIs

- IdemRecord, RequestHash, ResponseCache

- Filter/middleware around APIs

Concurrency

TTL store + hash compare

Pods & Scaling

Gateway pods; Redis cluster; HPA with API

Metrics / Deploy

`dup_hit_rate, mismatch_rate, redis_p99, key_cardinality` — alert on SLO burn (p99, error rate, saturation).

Rolling gateway; dual-read key format; rollback TTL config

Model / APIs

- Cart, LineItem, PriceContext, Calculator

- POST /price

Concurrency

Pure functions + versioned tax tables

Pods & Scaling

Stateless pods; cache tax tables; HPA on checkout QPS

Metrics / Deploy

`price_p99, mismatch_vs_order, cache_stale, cpu` — alert on SLO burn (p99, error rate, saturation).

Versioned calculator; canary; rollback by pin version header

Model / APIs

- RMA, State, RefundPort, RestockPort

- POST /rma, POST /rma/{id}/transition

Concurrency

FSM + outbox + idempotent refunds

Pods & Scaling

Pods + async refund workers; HPA on transitions

Metrics / Deploy

`transition_p99, refund_fail, stuck_state_count, worker_lag` — alert on SLO burn (p99, error rate, saturation).

Additive states only; flag new transitions; rollback by disabling transitions

Model / APIs

- GiftCard, LedgerEntry, Hold, Redemption, IdempotencyKey

- POST /cards/issue, /cards/{id}/hold, /redeem, /reverse

Concurrency

Optimistic version on balance; unique idempotency; holds with TTL; outbox for statements

Pods & Scaling

3–6 ledger pods; Redis idempotency; HPA on redeem p99 & CPU

Metrics / Deploy

redeem_p99_ms, negative_balance_violations, hold_expire_lag, idem_hit_rate

Expand/contract ledger schema; flag new FX path; rollback by disabling write path

Model / APIs

- SaleWindow, TokenBucket, AdmitDecision, Waitlist

- POST /sales/{id}/admit, GET /sales/{id}/remaining

Concurrency

Redis DECR/Lua or DB CAS on remaining; idempotent admit keys

Pods & Scaling

Stateless admit pods + Redis cluster; HPA on admit QPS; shed load with 429

Metrics / Deploy

admit_success_rate, oversell_count, redis_p99, shed_rate

Canary bucket size; dual-read remaining; instant flag kill switch

Model / APIs

- Product, CatalogVersion, AttributeSet, PublishJob

- POST /drafts, POST /publish, GET /products/{sku}?version=

Concurrency

Optimistic draft locks; atomic alias swap on publish

Pods & Scaling

Read-heavy CDN/cache; publish workers; HPA on read RPS

Metrics / Deploy

publish_fail_rate, read_p99, stale_serve_rate, index_lag

Blue-green version alias; dual-read during migrate; rollback alias pin

Model / APIs

- RateCard, Zone, CarrierAdapter, Quote, SurchargeRule

- POST /shipping/quote, GET /carriers

Concurrency

Pure calc + versioned rate tables; cache by address hash

Pods & Scaling

Stateless pods; cache rate cards; circuit-break carrier APIs

Metrics / Deploy

quote_p99, carrier_error_rate, cache_hit, mismatch_vs_label

Versioned rate pack; canary %; rollback pin rateCardVersion

Model / APIs

- Signal, FeatureStore, Score, Decision, Case

- POST /score, POST /cases/{id}/decision, GET /explanations/{id}

Concurrency

Idempotent score by orderId; async enrichers; timeout budgets

Pods & Scaling

Score pods + Kafka consumers; HPA on lag; isolate model CPU pool

Metrics / Deploy

score_p99, timeout_rate, false_positive_proxy, consumer_lag

Shadow model; canary traffic; flag rollback to previous model

Model / APIs

- Account, Ledger, EarnRule, BurnHold, Tier

- POST /earn, /burn/hold, /burn/confirm, GET /balance

Concurrency

Account version + unique eventId; holds expire; outbox to CRM

Pods & Scaling

Ledger pods; Redis balance cache with invalidate; HPA on earn QPS

Metrics / Deploy

balance_mismatch, earn_p99, hold_leak, cache_stale

Additive rules; dual-write old/new ledger; rollback flag on burn path

Model / APIs

- Store, Slot, Reservation, CapacityPolicy

- GET /stores/{id}/slots, POST /reserve, POST /cancel

Concurrency

Conditional capacity decrement; reservation TTL; unique customer+slot

Pods & Scaling

Regional pods near stores; Redis hot slots; HPA on reserve QPS

Metrics / Deploy

reserve_conflict_rate, overbook_count, cancel_lag, db_cpu

Expand slot schema; canary capacity policy; rollback policy config

Model / APIs

- Asset, UploadSession, ScanResult, Rendition, Invalidation

- POST /uploads/session, POST /uploads/{id}/complete, GET /assets/{id}

Concurrency

Session status FSM; idempotent complete; async workers

Pods & Scaling

API pods + scan/thumbnail workers; object store; HPA on queue depth

Metrics / Deploy

upload_fail_rate, scan_lag, rendition_p99, cdn_purge_fail

Rolling workers; additive rendition types; rollback by disabling new type

Goal / Capacity

Route orders to FC, allocate inventory, create shipments.

10M orders/day peak 3× → ~350 QPS avg, ~1k peak; p99 allocate <150ms.

Topology

API → Order → Inventory/Allocation → Kafka → WMS; Redis holds; Postgres by merchant.

Scaling

Scale workers on Kafka lag; shard inventory by FC.

Deployment / Metrics

Multi-AZ; rolling adapters; outbox; pause consumer to rollback.

p99, error rate, saturation, business SLIs.

Goal / Capacity

ATP with regional caches; strong reserve on write.

100M SKU×FC; 50k read QPS; 5k write QPS.

Topology

CQRS write ledger + reserve; project to Redis; version conflicts.

Scaling

HPA on reserve QPS; hot-SKU sticky routing.

Deployment / Metrics

Active-active reads; single-writer per SKU shard; blue-green projectors.

p99, error rate, saturation, business SLIs.

Goal / Capacity

Personalized feed <200ms p99.

DAU 20M; feed QPS 30k; features <15m fresh.

Topology

CDN → Feed API → candidates → ranker → popular fallback.

Scaling

Cache embeddings; CB degrade to popular.

Deployment / Metrics

Canary model; shadow traffic; flag rollback.

p99, error rate, saturation, business SLIs.

Goal / Capacity

Ingest, parse, index, tiered retention.

100k events/sec; freshness <60s.

Topology

Agents → Kafka → processors → OpenSearch + cold storage.

Scaling

Partition by service; DLQ; autoscale on lag.

Deployment / Metrics

Rolling processors; index aliases for reindex.

p99, error rate, saturation, business SLIs.

Goal / Capacity

Checkout across regions with conflict policy.

RPO≈0 cart; payments sticky; catalog eventual.

Topology

Global LB → regional stacks; async replication; conflict resolver.

Scaling

Traffic weights; cell architecture.

Deployment / Metrics

Region-by-region deploy; per-region flags; rollback traffic.

p99, error rate, saturation, business SLIs.

Capacity

Peak 50k checkout starts/sec; p99 reserve <120ms; payment timeout 3s; error budget 0.1%.

Topology

Edge CDN/WAF → API gateway → Checkout BFF → Cart/Inventory/Payment/Fraud; Kafka outbox; Redis holds.

Scaling

HPA on checkout QPS & queue lag; shed non-critical personalization; cell/shard by region.

Deploy / Metrics

Canary region; feature flags for optional steps; pause consumers to rollback; expand/contract schemas.

checkout_success_rate, reserve_p99, payment_timeout_rate, kafka_lag, pool_saturation

Capacity

100M docs; 20k QPS search; p99 <150ms; index lag <60s for price/ATP.

Topology

Ingest CDC/Kafka → indexers → OpenSearch clusters; query API + query cache + CDN for popular.

Scaling

Shard by category/hash; replica read pools; degrade facets under load; autocomplete separate index.

Deploy / Metrics

Index alias blue-green; dual-write analyzers; canary query parser; rollback alias.

search_p99, zero_result_rate, index_lag, cache_hit, cluster_cpu

Capacity

30k events/sec; score p99 <80ms hard path; async enrich <2s; review SLA 15m.