Home/DSA Complete from Scratch to Expert/dsa-topics

Arrays & Hashing

Master this topic with zero to advance depth.

Arrays & Hashing: The Storage & Retrieval Duo

Arrays and Hashing are the foundational building blocks of efficient data structures. Arrays provide O(1) indexing by memory address, while Hashing (via HashMaps and HashSets) provides average O(1) time for search, insertion, and deletion by mapping keys to indices.

1. Space-Time Complexity Overview

Operation	Array (Unsorted)	Array (Sorted)	Hash Map (Avg)
Access (Index)	$O(1)$	$O(1)$	$O(1)$
Search (Value)	$O(N)$	$O(\\log N)$	$O(1)$
Insertion	$O(1)$ (at end)	$O(N)$	$O(1)$
Deletion	$O(N)$	$O(N)$	$O(1)$

2. The Core Philosophy: Trade-offs

Most 'Arrays & Hashing' problems involve trading space for time. By storing information in a Hash Set or Map (extra space), we avoid nested loops and repetitive scans (saving time).

3. Essential Mental Models

The Warehouse (Array): Elements are stored in numbered aisles. If you know the aisle number, you find the item instantly ( $O(1)$ ). If you only know the item name, you must walk through every aisle ( $O(N)$ ).
The Librarian's Index (Hash Map): A card catalog that tells you exactly which aisle and shelf an item is on. Looking up the card is instant, even in a library with millions of books.

4. Key Patterns to Master

Frequency Snapshot: Use a Map (or int[26]) to count occurrences. If count becomes $>1$ , you found a duplicate.
The Signature Key: Grouping items by a shared property. For anagrams, the signature is the sorted string or character counts.
Prefix Sums: Transform an array into a "Running Total" array. Useful for finding sums of any subarray in $O(1)$ time.
Hole Filling/Cyclic Mapping: Using the array indices themselves as a "Set" when the values are in range $[1, N]$ . (e.g., nums[nums[i]-1] = -abs(...))
Sliding Window Hashing: Using a rolling hash or frequency map to track properties of a moving window.

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Visual Representation

nums = [2, 7, 11, 15], target = 9

1. Complement = target - current
2. Scan through array:
   - 2: Complement = 9-2 = 7. Not in map. Store {2: 0}
   - 7: Complement = 9-7 = 2. FOUND in map at index 0!
   Return [0, 1]

Easy

Examples

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Because nums[0] + nums[1] == 9, we return [0, 1].

Approach 1

Level I: Brute Force

Intuition

Try every possible pair of numbers in the array. This involves nested loops where the outer loop picks the first number and the inner loop looks for the second number that sums to the target.

⏱ O(N²)💾 O(1)

Detailed Dry Run

nums = [2, 7, 11], target = 9

i=0 (2), j=1 (7): 2+7=9. Found! Return [0, 1]

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[]{};
    }
}

Approach 2

Level II: Sorting + Two Pointers

Intuition

If the array is sorted, we can use two pointers (left and right). If their sum is smaller than target, move left pointer right; if larger, move right pointer left. Note: Since we need indices, we must keep track of original positions.

⏱ O(N log N) for sorting.💾 O(N) to store indices.

Detailed Dry Run

nums = [3, 2, 4], target = 6

Pairs with indices: [(3,0), (2,1), (4,2)]
Sort: [(2,1), (3,0), (4,2)]
L=0 (2), R=2 (4): sum=6. Found indices 1 and 2.

java

import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] pair = new int[nums.length][2];
        for(int i=0; i<nums.length; i++) { pair[i][0] = nums[i]; pair[i][1] = i; }
        Arrays.sort(pair, (a, b) -> Integer.compare(a[0], b[0]));
        int l = 0, r = nums.length - 1;
        while(l < r) {
            int sum = pair[l][0] + pair[r][0];
            if(sum == target) return new int[]{pair[l][1], pair[r][1]};
            if(sum < target) l++; else r--;
        }
        return new int[]{};
    }
}

Approach 3

Level III: HashMap (One-Pass)

Intuition

Trade space for time. As we iterate, we calculate the complement needed (target - current). If complement is already in map, we found the pair. Otherwise, store the current number's index in the map.

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [2, 7, 11], target = 9

n=2, comp=7. Map: {2: 0}
n=7, comp=2. Map contains 2 (idx 0). return [0, 1]

java

import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int comp = target - nums[i];
            if (map.containsKey(comp)) return new int[]{map.get(comp), i};
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Visual Representation

s = "anagram", t = "nagaram"

Method: Count each character
a: 3, n: 1, g: 1, r: 1, m: 1  (in s)
a: 3, n: 1, g: 1, r: 1, m: 1  (in t)

Counts Match -> True

Easy

Examples

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

Approach 1

Level I: Sorting

Intuition

Anagrams have the same characters in the same frequency. If we sort both strings, they should be identical.

⏱ O(N log N) where N is string length.💾 O(1) or O(N) depending on sort implementation.

Detailed Dry Run

s="abc", t="cba" s.sort() -> "abc" t.sort() -> "abc" "abc" == "abc" -> True

java

import java.util.Arrays;
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }
}

Approach 2

Level II: HashMap (Character Count)

Intuition

Count character frequencies using a HashMap. This handles Unicode characters more naturally than a fixed-size array.

⏱ O(N)💾 O(1) - finite character set size.

Detailed Dry Run

s="aa", t="a" Map {a: 2} from s Map {a: 2-1=1} from t Length mismatch detected early -> return False

java

import java.util.*;
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> count = new HashMap<>();
        for (char x : s.toCharArray()) count.put(x, count.getOrDefault(x, 0) + 1);
        for (char x : t.toCharArray()) {
            if (!count.containsKey(x) || count.get(x) == 0) return false;
            count.put(x, count.get(x) - 1);
        }
        return true;
    }
}

Approach 3

Level III: Fixed-Size Array (Optimal)

Intuition

Since we only have 26 lowercase letters, an array of size 26 is more efficient than a HashMap.

⏱ O(N)💾 O(1) - fixed 26 integers.

Detailed Dry Run

arr = [0]*26 s="a": arr[0]++ -> [1,0...] t="a": arr[0]-- -> [0,0...] All indices zero -> True

java

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }
}

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Visual Representation

nums = [1, 2, 3, 1]

Using HashSet:
- 1: Not in set. Set={1}
- 2: Not in set. Set={1, 2}
- 3: Not in set. Set={1, 2, 3}
- 1: EXISTS in set! -> Return True

Easy

Examples

Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Approach 1

Level I: Brute Force

Intuition

Compare every pair of elements. If any pair is identical, return true.

⏱ O(N²)💾 O(1)

Detailed Dry Run

[1, 2, 1] (1, 2): No (1, 1): MATCH! True

java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

Approach 2

Level II: Sorting

Intuition

If duplicates exist, they will be adjacent when sorted.

⏱ O(N log N)💾 O(1) if sorting in-place.

Detailed Dry Run

[1, 2, 3, 1] -> Sort -> [1, 1, 2, 3] nums[0] == nums[1] (1 == 1) -> True

java

import java.util.Arrays;
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i+1]) return true;
        }
        return false;
    }
}

Approach 3

Level III: HashSet (Optimal)

Intuition

Checking membership in a HashSet takes O(1) average time. If an element is already in the set, a duplicate is found.

⏱ O(N)💾 O(N)

Detailed Dry Run

[1, 2, 3, 1] Map {} -> {1} -> {1, 2} -> {1, 2, 3} -> Contains 1! True

java

import java.util.*;
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)) return true;
            set.add(n);
        }
        return false;
    }
}

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Visual Representation

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

1. Sort each string to create a 'key':
   "eat" -> "aet"
   "tea" -> "aet"
   "tan" -> "ant"
   ...

2. Group by key in a Hash Map:
   "aet" -> ["eat", "tea", "ate"]
   "ant" -> ["tan", "nat"]
   "abt" -> ["bat"]

Medium

Examples

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
"eat", "tea", and "ate" are anagrams. "tan" and "nat" are anagrams. "bat" is alone.

Approach 1

Level I: Brute Force (Compare All Pairs)

Intuition

Compare every string with every other string to check if they are anagrams. We use a used boolean array to keep track of strings that have already been grouped. This is the simplest baseline approach but inefficient for large inputs.

⏱ O(N² * K log K) where N is the number of strings and K is the average length of strings (due to sorting for comparison).💾 O(N * K) to store the result.

Detailed Dry Run

String A	String B	Sorted(A)	Sorted(B)	Is Anagram?
"eat"	"tea"	"aet"	"aet"	Yes
"eat"	"tan"	"aet"	"ant"	No
"tan"	"nat"	"ant"	"ant"	Yes

java

import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        boolean[] used = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            if (used[i]) continue;
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            used[i] = true;
            for (int j = i + 1; j < strs.length; j++) {
                if (!used[j] && areAnagrams(strs[i], strs[j])) {
                    group.add(strs[j]);
                    used[j] = true;
                }
            }
            res.add(group);
        }
        return res;
    }

    private static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1, c2);
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

Approach 2

Level II: Better Solution (HashMap with Sorted String Key)

Intuition

Instead of nested loops, we use a Hash Map. Since all anagrams share the same sorted version, we sort each string and use it as a key. All strings that result in the same sorted string are added to the same list.

⏱ O(N * K log K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map.

Detailed Dry Run

Input String	Sorted Key	Action
"eat"	"aet"	Map["aet"] = ["eat"]
"tea"	"aet"	Map["aet"] = ["eat", "tea"]
"tan"	"ant"	Map["ant"] = ["tan"]

java

import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

Approach 3

Level III: Optimal Solution (Frequency Bucket Key)

Intuition

Instead of sorting each string ( $O(K \log K)$ ), we can use the character frequencies (26 characters) as the Hash Map key. This reduces the transformation time to linear $O(K)$ . We represent the count array as a string or tuple to use as a key.

⏱ O(N * K) where N is the number of strings and K is the maximum length of a string.💾 O(N * K) to store the Hash Map and count strings.

Detailed Dry Run

Bucket Count Key

Char	Frequency Count Array
eat	[1, 0, 0, 0, 1, ..., 1, ...] (a:1, e:1, t:1)
tea	[1, 0, 0, 0, 1, ..., 1, ...] (same signature)

Logic: key = "#1#0#0...#1". Anagrams share the same key without ever sorting.

java

import java.util.*;

public class Main {
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        System.out.println(groupAnagrams(strs));
    }
}

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in $O(n)$ time.

Visual Representation

nums = [100, 4, 200, 1, 3, 2]

Step 1: Put all in HashSet: {100, 4, 200, 1, 3, 2}
Step 2: Check each number if it's a START (num-1 not in set):
   - 100: (99? No) -> Start! Count 101, 102... (Len: 1)
   - 4:   (3? Yes) -> Not a start.
   - 200: (199? No) -> Start! Count 201... (Len: 1)
   - 1:   (0? No)  -> Start! Count 2, 3, 4 (Len: 4) -> MAX!

Medium

Examples

Input: nums = [100,4,200,1,3,2]
Output: 4
The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
The longest consecutive elements sequence is [0,1,2,3,4,5,6,7,8].

Approach 1

Level I: Brute Force (Check Each Number)

Intuition

For every number x in the array, we check if it is the start of a sequence by trying to find x+1, x+2, etc., using a linear scan through the array for each step. This leads to a cubic time complexity.

⏱ O(N³) because we have a loop for each number, a loop for the sequence length, and a linear scan `contains` check.💾 O(1)

Detailed Dry Run

Num	Sequence	Max Length
100	[100] (101 not found)	1
4	[4] (5 not found)	1
1	[1, 2, 3, 4]	4

java

import java.util.*;

public class Main {
    private static boolean contains(int[] nums, int target) {
        for (int n : nums) if (n == target) return true;
        return false;
    }
    
    public static int longestConsecutive(int[] nums) {
        int longest = 0;
        for (int num : nums) {
            int curr = num;
            int streak = 1;
            while (contains(nums, curr + 1)) {
                curr++;
                streak++;
            }
            longest = Math.max(longest, streak);
        }
        return longest;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

Approach 2

Level II: Better Solution (Sorting)

Intuition

By sorting the array, consecutive numbers are placed adjacent to each other. We can then find sequences by comparing each element with its predecessor. We must handle duplicate elements by skipping them during the streak calculation.

⏱ O(N log N) dominated by sorting the array.💾 O(1) (or O(N) depending on sort implementation).

Detailed Dry Run

Sorted Array	Comparison	Action	Streak
[1, 2, 3, 4, 100, 200]	2 == 1+1	Increment	2
[1, 2, 3, 4, 100, 200]	100 != 4+1	Reset	1

java

import java.util.*;

public class Main {
    public static int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int longest = 1, curr = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) continue;
            if (nums[i] == nums[i-1] + 1) curr++;
            else {
                longest = Math.max(longest, curr);
                curr = 1;
            }
        }
        return Math.max(longest, curr);
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

Approach 3

Level III: Optimal Solution (HashSet)

Intuition

To achieve linear time, we use a Hash Set for $O(1)$ lookups. The key insight is identifying the start of a sequence: a number x is the start if x-1 does not exist in the set. Only then we explore the sequence using a while loop, ensuring each element is visited at most twice.

⏱ O(N) because each number is visited at most twice (once in the main loop and once in a `while` loop).💾 O(N) to store the elements in the Hash Set.

Detailed Dry Run

Start-of-Sequence Logic

Number	x-1 In Set?	Action	Streak
100	99 (No)	Start Streak	1
4	3 (Yes)	Skip (not start)	-
1	0 (No)	Start Streak	4 (1,2,3,4)

Visual: [1] -> [2] -> [3] -> [4] (Sequence identified from 1)

java

import java.util.*;

public class Main {
    public static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int longest = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) { // Only start if it's the beginning
                int curr = n, streak = 1;
                while (set.contains(curr + 1)) {
                    curr++; streak++;
                }
                longest = Math.max(longest, streak);
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
}

Product of Array Except Self

The product of all elements except nums[i] is (product of all elements to the left of i) * (product of all elements to the right of i). We can precalculate these products in one or two passes.

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operator.

Visual Representation

nums = [1, 2, 3, 4]

Prefixes: [1,  1,  1*2, 1*2*3] = [1,  1,  2,  6]
Suffixes: [2*3*4, 3*4, 4,  1] = [24, 12, 4,  1]

Result:   [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]

Medium

Examples

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
answer[0] = 234 = 24, answer[1] = 134 = 12, answer[2] = 124 = 8, answer[3] = 123 = 6

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Any product that includes 0 will be 0

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each index i, we iterate through the entire array again using index j. If i != j, we multiply nums[j] to a running product. This is suboptimal due to the nested traversal.

⏱ O(N²) because for every element, we scan the rest of the array.💾 O(1) (excluding output array)

Detailed Dry Run

Index	Elements Multiplied	Result
0	2 * 3 * 4	24
1	1 * 3 * 4	12
2	1 * 2 * 4	8
3	1 * 2 * 3	6

java

import java.util.*;

public class Main {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) prod *= nums[j];
            }
            res[i] = prod;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(nums)));
    }
}

Approach 2

Level II: Better Solution (Prefix & Suffix Arrays)

Intuition

Any element at i has a product equal to (everything to its left) * (everything to its right). We can precompute two arrays: prefix (cumulative product from start) and suffix (cumulative product from end).

⏱ O(N) traversal.💾 O(N) storage.

Detailed Dry Run

Index	Prefix (Left)	Suffix (Right)	Left * Right
0	1	234 = 24	24
1	1	3*4 = 12	12
2	1*2 = 2	4	8
3	123 = 6	1	6

java

import java.util.*;

public class Main {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        left[0] = 1; right[n-1] = 1;
        for (int i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1];
        for (int i = n-2; i >= 0; i--) right[i] = right[i+1] * nums[i+1];
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = left[i] * right[i];
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(nums)));
    }
}

Approach 3

Level III: Optimal Solution (Space Optimized)

Intuition

We can optimize space by using the result array itself to store prefix products first. Then, we iterate backwards and maintain a running suffix product to multiply with the stored prefix values. This avoids extra arrays.

⏱ O(N) with only two passes.💾 O(1) extra space.

Detailed Dry Run

Optimization Visual

nums = [1, 2, 3, 4]

Forward Pass (Prefix): res = [1, 1, 2, 6] (Storing products of everything to the left)

Backward Pass (Suffix):

i	res[i] (Prefix)	Suffix Var	res[i] * Suffix (Final)
3	6	1	6
2	2	1*4=4	8
1	1	4*3=12	12
0	1	12*2=24	24

Visual Representation:

Index:   0    1    2    3
Nums:    1    2    3    4
Prefix: [1,   1,   2,   6]
Suffix: [24,  12,  4,   1]
Result: [24,  12,  8,   6]

java

import java.util.*;

public class Main {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) res[i] = res[i-1] * nums[i-1];
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= suffix;
            suffix *= nums[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(nums)));
    }
}

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Visual Representation

nums = [1, 1, 1, 2, 2, 3], k = 2

Frequency Map: {1: 3, 2: 2, 3: 1}

Buckets (Count -> Elements):
1: [3]
2: [2]
3: [1]

Collect from largest count: [1, 2]

Medium

Examples

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 appears 3 times, 2 appears 2 times. The top 2 most frequent elements are [1, 2].

Input: nums = [1], k = 1
Output: [1]
1 is the only element, so it's the most frequent.

Approach 1

Level I: Brute Force (Sorting Map)

Intuition

Count the frequency of each element using a Hash Map. Convert the map entries into a list and sort the list based on frequencies in descending order. Finally, extract the first k elements.

⏱ O(N log N) dominated by sorting the map entries.💾 O(N) to store frequencies in the Hash Map.

Detailed Dry Run

Element	Frequency	Sorted Rank
1	3	1
2	2	2
3	1	3

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((a, b) -> map.get(b) - map.get(a));
        
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = list.get(i);
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

Approach 2

Level II: Better Solution (Min-Heap)

Intuition

Maintain a Min-Heap of size k. If we find an element with a higher frequency than the heap's smallest (root), we replace it. This ensures that after processing all elements, the heap contains the k most frequent ones.

⏱ O(N log K) as heap operations take $O(\log K)$ for each map entry.💾 O(N) to store frequencies in the map.

Detailed Dry Run

Heap Evolution (k=2)

Step	Element (Freq)	Heap State	Action
1	1 (3)	[(1,3)]	Push
2	2 (2)	[(2,2), (1,3)]	Push
3	3 (1)	[(3,1), (1,3), (2,2)]	Push & Pop Root (3,1)

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (int n : map.keySet()) {
            heap.add(n);
            if (heap.size() > k) heap.poll();
        }
        
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = heap.poll();
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

Approach 3

Level III: Optimal Solution (Bucket Sort)

Intuition

Frequencies range from 0 to N (length of array). We can create an array of buckets where buckets[i] contains all numbers that appear i times. By iterating through buckets from N down to 0, we can collect the top k elements in linear time.

⏱ O(N) to count frequencies and populate buckets.💾 O(N) for map and buckets.

Detailed Dry Run

Bucket Sort Visual

nums = [1,1,1,2,2,3], k = 2 Freq Map: {1:3, 2:2, 3:1}

Freq (Bucket Index)	Numbers
3	[1]
2	[2]
1	[3]

Collection (Right to Left):

Freq 3: Add 1 -> res = [1]
Freq 2: Add 2 -> res = [1, 2]
len(res) == k, STOP.

java

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int n : map.keySet()) {
            int freq = map.get(n);
            if (bucket[freq] == null) bucket[freq] = new ArrayList<>();
            bucket[freq].add(n);
        }
        
        int[] res = new int[k];
        int count = 0;
        for (int i = bucket.length - 1; i >= 0 && count < k; i--) {
            if (bucket[i] != null) {
                for (int n : bucket[i]) {
                    res[count++] = n;
                    if (count == k) return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topKFrequent(nums, 2)));
    }
}

Subarray Sum Equals K

The sum of subarray nums[i...j] is PrefixSum[j] - PrefixSum[i-1]. If this difference equals k, then PrefixSum[j] - k = PrefixSum[i-1]. We use a HashMap to count occurrences of PrefixSum[i-1].

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Visual Representation

nums = [1, 2, 3], k = 3

Subarrays:
[1, 2] -> Sum = 3 (Valid)
[3]    -> Sum = 3 (Valid)

Answer: 2

Medium

Examples

Input: nums = [1,1,1], k = 2
Output: 2
The subarrays [1,1] and [1,1] have sum 2.

Input: nums = [1,2,3], k = 3
Output: 2
The subarrays [1,2] and [3] have sum 3.

Approach 1

Level I: Brute Force (All Subarrays)

Intuition

We check every possible subarray by iterating through all pairs of start indices i and end indices j. For each pair, we calculate the sum of elements from i to j. If the sum equals k, we increment our count.

⏱ O(N²) after optimizing the inner sum loop.💾 O(1) extra space.

Detailed Dry Run

i	j	Subarray	Sum	Count
0	0	[1]	1	0
0	1	[1, 1]	2	1 (k=2)
1	1	[1]	1	1
1	2	[1, 1]	2	2 (k=2)

java

import java.util.*;

public class Main {
    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        System.out.println(subarraySum(nums, 2));
    }
}

Approach 2

Level II: Better Solution (Cumulative Sum O(N²))

Avoid the inner sum loop by adding nums[j] to the current running sum as you expand the subarray.

⏱ O(N²)💾 O(1)

Detailed Dry Run

j	Running Sum	k=2?
0	1	No
1	2	Yes
2	3	No

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

Approach 3

Level III: Optimal Solution (Prefix Sum + HashMap)

Intuition

The sum of subarray nums[i...j] is PrefixSum[j] - PrefixSum[i-1]. If this difference equals k, then PrefixSum[j] - k = PrefixSum[i-1]. We use a HashMap to store the frequencies of prefix sums encountered so far. For each new PrefixSum[j], we check how many times PrefixSum[j] - k has appeared before.

⏱ O(N) single pass traversal.💾 O(N) to store prefix sums in the map.

Detailed Dry Run

Prefix Sum Visual

nums = [1, 2, 3], k = 3 Initial Map: {0: 1} (Subarray with sum 0 starts from beginning)

Index	Num	Current Prefix Sum (S)	Target (S - k)	Found in Map?	New Map State	Count
0	1	1	-2	No	`{0:1, 1:1}`	0
1	2	3	0	Yes (freq 1)	`{0:1, 1:1, 3:1}`	1
2	3	6	3	Yes (freq 1)	`{0:1, 1:1, 3:1, 6:1}`	2

java

import java.util.*;

public class Main {
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0, sum = 0;
        for (int n : nums) {
            sum += n;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(subarraySum(nums, 3));
    }
}

Find All Duplicates in an Array

Since all integers are in the range [1, n], we can use the array itself as a frequency map by negating values at indices corresponding to the numbers seen. If we encounter an already negative value, it's a duplicate.

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice. You must solve the problem without using extra space and in O(n) runtime.

Visual Representation

nums = [4, 3, 2, 7, 8, 2, 3, 1]

Index 0 (4): Mark index 3 -> [4, 3, 2, -7, 8, 2, 3, 1]
Index 1 (3): Mark index 2 -> [4, 3, -2, -7, 8, 2, 3, 1]
...
Index 5 (2): Index 1 is already negative (-3)! DUPLICATE FOUND: 2

Medium

Examples

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
2 and 3 appear twice in the array.

Input: nums = [1,1,2]
Output: [1]
1 appears twice.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

We check every element against all subsequent elements to find duplicates. If a match is found, we add it to our result list (handling duplicates in the result list if necessary).

⏱ O(N²) where N is the length of the array.💾 O(1) (excluding the space for the result list).

Detailed Dry Run

i	j	nums[i]	nums[j]	Match?	Result
0	1	4	3	No	[]
2	5	2	2	Yes	[2]
1	6	3	3	Yes	[2, 3]

java

import java.util.*;

public class Main {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    if (!res.contains(nums[i])) res.add(nums[i]);
                    break;
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(findDuplicates(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}

Approach 2

Level II: HashSet / Frequency Array

Intuition

Use an auxiliary Hash Set or boolean array to track which numbers have been seen so far. If a number is already in the set, it's a duplicate.

⏱ O(N) traversal.💾 O(N) for the Hash Set.

Detailed Dry Run

Num	Seen?	Action	Result
4	No	Add to Set	[]
3	No	Add to Set	[]
2	No	Add to Set	[]
2	YES	Add to Result	[2]

java

public List<Integer> findDuplicates(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> res = new ArrayList<>();
    for (int n : nums) {
        if (seen.contains(n)) res.add(n);
        else seen.add(n);
    }
    return res;
}

Approach 3

Level III: Optimal Solution (In-place Negation)

Intuition

Since all integers are in the range [1, n], we can use the array itself as a hash table. For each number x, we go to the index abs(x)-1. If the value at that index is already negative, we know we've seen x before, so x is a duplicate. Otherwise, we negate the value to 'mark' it as seen.

⏱ O(N) single pass through the array.💾 O(1) extra space (modifying the input array in-place).

Detailed Dry Run

Marking Process

nums = [4, 3, 2, 7, 8, 2, 3, 1]

[4, 3, 2, 7, 8, 2, 3, 1]  Iter 1: x=4, Mark index 3 (4-1)
          ^
[4, 3, 2, -7, 8, 2, 3, 1] Iter 5: x=2, index 1 (2-1) is 3 (>0), mark
    ^
[4, -3, 2, -7, 8, 2, 3, 1] Iter 6: x=2, index 1 is -3 (<0). FOUND DUPLICATE!

| Num (x) | Index (|x|-1) | Value at Index | Action | Result | | :--- | :--- | :--- | :--- | :--- | | 4 | 3 | 7 | Mark: nums[3]=-7 | [] | | 3 | 2 | 2 | Mark: nums[2]=-2 | [] | | 2 | 1 | 3 | Mark: nums[1]=-3 | [] | | 7 | 6 | 3 | Mark: nums[6]=-3 | [] | | 2 | 1 | -3 | Already Negative! | [2] |

java

import java.util.*;

public class Main {
    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] < 0) res.add(Math.abs(nums[i]));
            else nums[index] = -nums[index];
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(findDuplicates(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
    }
}

Set Matrix Zeroes

If an element is 0, we must mark its row and column. To do this in-place, we can use the first row and first column of the matrix itself as auxiliary storage (flags).

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.

Visual Representation

Matrix:
[1, 1, 1]
[1, 0, 1]
[1, 1, 1]

Output:
[1, 0, 1]
[0, 0, 0]
[1, 0, 1]

Medium

Examples

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
The element at (1,1) is 0, so row 1 and column 1 are set to 0.

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Elements at (0,0) and (0,3) are 0, so their rows and columns are set to 0.

Approach 1

Level I: Brute Force (Extra Matrix)

Intuition

Create a copy of the matrix. If an element in the original is 0, set the entire row and column in the copy to 0. This is simple but uses O(M*N) extra space and involves redundant work.

⏱ O(M*N * (M+N)) where M and N are dimensions of the matrix.💾 O(M*N) for the copy matrix.

Detailed Dry Run

Matrix Copy Trace

matrix = [[1, 0], [1, 1]]

copy = [[1, 0], [1, 1]]
Find 0 at (0, 1)
In copy: Set row 0 to 0s, col 1 to 0s.
copy becomes [[0, 0], [1, 0]]
Update original matrix with copy values.

java

import java.util.Arrays;

public class Main {
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] copy = new int[m][n];
        for (int i = 0; i < m; i++) copy[i] = matrix[i].clone();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    for (int k = 0; k < n; k++) copy[i][k] = 0;
                    for (int k = 0; k < m; k++) copy[k][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) matrix[i] = copy[i];
    }
    public static void main(String[] args) {
        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        setZeroes(matrix);
        System.out.println(Arrays.deepToString(matrix));
    }
}

Approach 2

Level II: Row and Column Auxiliary Arrays

Intuition

We can improve the space complexity by using two auxiliary boolean arrays: row of size m and col of size n. If matrix[i][j] == 0, we set row[i] = true and col[j] = true. Finally, we traverse the matrix again and set matrix[i][j] = 0 if row[i] or col[j] is true.

⏱ O(M*N) two passes through the matrix.💾 O(M+N) for the auxiliary arrays.

Detailed Dry Run

Row Flags	Col Flags	i, j	Action
[F, T, F]	[F, T, F]	1, 1	matrix[1][1]=0, so row[1]=T, col[1]=T
[F, T, F]	[F, T, F]	0, 1	row[0]=F, col[1]=T -> matrix[0][1]=0

java

public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean[] row = new boolean[m], col = new boolean[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) { row[i] = true; col[j] = true; }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) matrix[i][j] = 0;
        }
    }
}

Approach 3

Level III: Optimal Solution (In-place Flags)

Intuition

Use the first row and first column of the matrix itself to store flags for which rows and columns should be zeroed.

Use two variables row0 and col0 to track if the first row and column themselves need to be zeroed.
Iterate through the rest of the matrix, and if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
Finally, zero out cells based on flags, then the first row/column.

⏱ O(M*N) two passes through the matrix.💾 O(1) extra space.

Detailed Dry Run

Visual Process

matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

Initial Scan:
Found 0 at (1, 1) -> Mark First Row/Col
[1, 0, 1]  (matrix[0][1] = 0)
[0, 0, 1]  (matrix[1][0] = 0)
[1, 1, 1] 

Final Update (excluding row0/col0):
[1, 0, 1] 
[0, 0, 0] (Row 1 was marked)
[1, 0, 1] (Col 1 was marked)

java

import java.util.Arrays;

public class Main {
    public static void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row0 = false, col0 = false;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) col0 = true;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) row0 = true;
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if (col0) for (int i = 0; i < m; i++) matrix[i][0] = 0;
        if (row0) for (int j = 0; j < n; j++) matrix[0][j] = 0;
    }
    public static void main(String[] args) {
        int[][] matrix = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        setZeroes(matrix);
        System.out.println(Arrays.deepToString(matrix));
    }
}

Maximum Sum of Two Non-Overlapping Subarrays

To find two non-overlapping subarrays with lengths L and M that give the maximum sum, we consider two cases: subarray L comes before M, or M comes before L. We use prefix sums to calculate subarray sums in O(1) and track the maximum sum seen so far.

Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of two non-overlapping subarrays with lengths firstLen and secondLen. The subarrays must be non-overlapping, meaning they don't share any index.

Visual Representation

nums = [0, 6, 5, 2, 2, 5, 1, 9, 4], firstLen = 1, secondLen = 2

Possible Selections:
[6] and [1, 9] -> Sum = 6 + 10 = 16
[0] and [9, 4] -> Sum = 0 + 13 = 13
[9] and [6, 5] -> Sum = 9 + 11 = 20 (MAX!)

Medium

Examples

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Approach 1

Level I: Brute Force (Iterate All Subarrays)

Intuition

Iterate through all possible start positions for the first subarray of length firstLen. For each position, iterate through all possible start positions for the second subarray of length secondLen. Check if the two subarrays overlap; if not, calculate their sum and update the maximum.

⏱ O(N² * (L+M)) where N is array length, L and M are subarray lengths, due to repeated sum calculation.💾 O(1) extra space.

Detailed Dry Run

Sub1 (L=1)	Sub2 (M=2)	Total Sum	Max
[9] at i=7	[0,6] at j=0	9+11=20	20
[9] at i=7	[4] at j=8	OOB	20

java

public class Main {
    public static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int maxTotal = 0;
        int n = nums.length;
        for (int i = 0; i <= n - firstLen; i++) {
            int sum1 = 0;
            for (int k = 0; k < firstLen; k++) sum1 += nums[i + k];
            for (int j = 0; j <= n - secondLen; j++) {
                if (j + secondLen <= i || j >= i + firstLen) {
                    int sum2 = 0;
                    for (int l = 0; l < secondLen; l++) sum2 += nums[j + l];
                    maxTotal = Math.max(maxTotal, sum1 + sum2);
                }
            }
        }
        return maxTotal;
    }
    public static void main(String[] args) {
        int[] nums = {0,6,5,2,2,5,1,9,4};
        System.out.println(maxSumTwoNoOverlap(nums, 1, 2)); // Output: 20
    }
}

Approach 2

Level II: Better Solution (Prefix Sum + Nested Loops)

Intuition

Use prefix sums to calculate any subarray sum in O(1) time. This eliminates the inner loop for sum calculation but still requires O(N²) to check all pairs of non-overlapping subarrays.

⏱ O(N²) to iterate all pairs of subarray starting positions.💾 O(N) for the prefix sum array.

Detailed Dry Run

prefix[i+L]-prefix[i]	prefix[j+M]-prefix[j]	Action
sum(1) = 9	sum(2) = 11	total = 20
sum(1) = 4	sum(2) = 10	total = 14

java

public class Main {
    public static int maxSumTwoNoOverlap(int[] nums, int L, int M) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        int maxTotal = 0;
        for (int i = 0; i <= n - L; i++) {
            int sumL = prefix[i + L] - prefix[i];
            for (int j = 0; j <= n - M; j++) {
                if (j + M <= i || j >= i + L) {
                    int sumM = prefix[j + M] - prefix[j];
                    maxTotal = Math.max(maxTotal, sumL + sumM);
                }
            }
        }
        return maxTotal;
    }
    public static void main(String[] args) {
        int[] nums = {3,8,1,3,2,1,8,9,0};
        System.out.println(maxSumTwoNoOverlap(nums, 3, 2)); // Output: 29
    }
}

Approach 3

Level III: Optimal Solution (Prefix Sum + Sliding Window)

Intuition

Maintain the maximum sum of a subarray of length L seen so far as we iterate through possible positions of a following subarray of length M. We repeat this with L following M to cover both cases. This gives O(N) by visiting each element once.

⏱ O(N) single pass for each of the two cases.💾 O(N) for prefix sums (can be O(1) with optimized sliding window).

Detailed Dry Run

Sliding Window Max Sum (L=1, M=2)

nums = [0, 6, 5, 2, 2, 5]

Pass 1 (L before M):
[0] [6, 5] 2  2  5  -> sumL=0, maxL=0, sumM=11, res=11
 0 [6] [5, 2] 2  5  -> sumL=6, maxL=6, sumM=7, res=max(11, 13)=13
 0  6 [5] [2, 2] 5  -> sumL=5, maxL=6, sumM=4, res=max(13, 10)=13

java

public class Main {
    public static int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(
            helper(nums, firstLen, secondLen),
            helper(nums, secondLen, firstLen)
        );
    }
    
    private static int helper(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        
        int maxFirst = 0;
        int result = 0;
        for (int i = firstLen; i <= n - secondLen; i++) {
            maxFirst = Math.max(maxFirst, prefix[i] - prefix[i - firstLen]);
            result = Math.max(result, maxFirst + (prefix[i + secondLen] - prefix[i]));
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {0,6,5,2,2,5,1,9,4};
        System.out.println(maxSumTwoNoOverlap(nums, 1, 2)); // Output: 20
    }
}

Merge K Sorted Arrays

Merging multiple sorted arrays can be done efficiently using a Min-Heap. By keeping the current element of each array in the heap, we can always extract the smallest element in O(log K) time. Alternatively, Divide and Conquer can merge them in pairs.

You are given k sorted arrays. Merge all the arrays into one sorted array and return it.

Visual Representation

Arrays:
[1, 4, 5]
[1, 3, 4]
[2, 6]

Heap state (Min-Heap of elements from each array):
[1, 1, 2] -> Pop 1
[4, 1, 2] -> Pop 1
[4, 3, 2] -> Pop 2
...
Result: [1, 1, 2, 3, 4, 4, 5, 6]

Hard

Examples

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Merging the three lists: [1,4,5], [1,3,4], [2,6] results in [1,1,2,3,4,4,5,6].

Input: lists = []
Output: []
Empty list.

Approach 1

Level I: Brute Force (Flatten and Sort)

Intuition

Collect all elements from all K arrays into a single list, sort that list, and return it. This is simple but doesn't take advantage of the fact that each individual array is already sorted.

⏱ O(N log N) where N is the total number of elements.💾 O(N) to store all elements in a new list.

Detailed Dry Run

All Elements	Sorted Result
[1,4,5, 1,3,4, 2,6]	[1,1,2,3,4,4,5,6]

java

import java.util.*;

public class Main {
    public static int[] mergeKSortedArrays(int[][] arrays) {
        List<Integer> list = new ArrayList<>();
        for (int[] arr : arrays) {
            for (int val : arr) list.add(val);
        }
        Collections.sort(list);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) result[i] = list.get(i);
        return result;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}

Approach 2

Level II: Better Solution (Divide and Conquer)

Intuition

Merge the K arrays in pairs. In the first pass, merge array 1 with 2, 3 with 4, etc. Repeat this process until only one sorted array remains. This reduces the number of arrays logarithmically (log K).

⏱ O(N log K) where N is total elements and K is number of arrays.💾 O(N) for the result array.

Detailed Dry Run

Step	Pairs Merged	Result Arrays
1	[1,4,5] + [1,3,4]	[1,1,3,4,4,5]
1	[2,6]	[2,6]
2	[1,1,3,4,4,5] + [2,6]	[1,1,2,3,4,4,5,6]

java

import java.util.*;

public class Main {
    public static int[] mergeKSortedArrays(int[][] arrays) {
        if (arrays.length == 0) return new int[0];
        return mergeSort(arrays, 0, arrays.length - 1);
    }
    private static int[] mergeSort(int[][] arrays, int left, int right) {
        if (left == right) return arrays[left];
        int mid = left + (right - left) / 2;
        int[] l = mergeSort(arrays, left, mid);
        int[] r = mergeSort(arrays, mid + 1, right);
        return mergeTwo(l, r);
    }
    private static int[] mergeTwo(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            res[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
        }
        while (i < a.length) res[k++] = a[i++];
        while (j < b.length) res[k++] = b[j++];
        return res;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}

Approach 3

Level III: Optimal Solution (Min Heap)

Intuition

Use a Min-Heap to store the first element of each array along with its source array index and element index. Repeatedly extract the minimum element and insert the next element from the same array into the heap.

⏱ O(N log K) where N is total elements and K is number of arrays.💾 O(K) for the Min-Heap.

Detailed Dry Run

Min-Heap Merge Process

arrays = [[1, 4], [1, 3], [2, 6]]

Heap (val, array_idx, element_idx):
Push roots: [(1,0,0), (1,1,0), (2,2,0)]
Pop (1,0,0) -> Res: [1]. Push (4,0,1). Heap: [(1,1,0), (2,2,0), (4,0,1)]
Pop (1,1,0) -> Res: [1, 1]. Push (3,1,1). Heap: [(2,2,0), (3,1,1), (4,0,1)]

java

import java.util.*;

public class Main {
    static class Element {
        int val, arrayIdx, elemIdx;
        Element(int v, int a, int e) { val = v; arrayIdx = a; elemIdx = e; }
    }
    public static int[] mergeKSortedArrays(int[][] arrays) {
        PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        int totalSize = 0;
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                minHeap.offer(new Element(arrays[i][0], i, 0));
                totalSize += arrays[i].length;
            }
        }
        int[] result = new int[totalSize];
        int k = 0;
        while (!minHeap.isEmpty()) {
            Element curr = minHeap.poll();
            result[k++] = curr.val;
            if (curr.elemIdx + 1 < arrays[curr.arrayIdx].length) {
                minHeap.offer(new Element(arrays[curr.arrayIdx][curr.elemIdx + 1], curr.arrayIdx, curr.elemIdx + 1));
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] arrays = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        System.out.println(Arrays.toString(mergeKSortedArrays(arrays)));
    }
}

First Missing Positive

The missing positive must be in the range [1, n+1]. We can use the array itself to store presence information by placing each number x at index x-1. This is a constant space alternative to a HashSet.

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.

Visual Representation

nums = [3, 4, -1, 1]

Cyclic Sort (Move nums[i] to index nums[i]-1):
1. swap(3, -1) -> [-1, 4, 3, 1]
2. swap(4, 1)  -> [-1, 1, 3, 4]
3. swap(-1, 1) -> [1, -1, 3, 4]

Result:
Index 0: 1 (Correct)
Index 1: -1 (Incorrect! Should be 2)
Return: 2

Hard

Examples

Input: nums = [1,2,0]
Output: 3
The numbers in the range [1,2] are all in the array. 3 is the smallest missing positive.

Input: nums = [3,4,-1,1]
Output: 2
1 is in the array, but 2 is missing.

Approach 1

Level I: Brute Force (Sorting)

Intuition

Sort the input array. Since we are looking for the smallest missing positive integer (starting from 1), iterate through the sorted array and keep track of a target (starting at 1). If the current number equals target, increment target. If we find a number greater than target or reach the end, target is the answer.

⏱ O(N log N) due to sorting.💾 O(1) if sorting is in-place, otherwise O(N).

Detailed Dry Run

nums	target	Action
[3,4,-1,1]	1	Sort -> [-1,1,3,4]
-1	1	Skip (not positive)
1	1	Match! target -> 2
3	2	3 > 2, Stop.
Result: 2	-	-

java

import java.util.Arrays;

public class Main {
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int target = 1;
        for (int num : nums) {
            if (num == target) target++;
            else if (num > target) break;
        }
        return target;
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums)); // Output: 2
    }
}

Approach 2

Level II: Better Solution (HashSet)

Intuition

Store all numbers in a HashSet for O(1) lookups. Iterate from 1 up to N+1 (where N is array size). The first number not present in the set is the smallest missing positive integer.

⏱ O(N) to populate the set and iterate up to N+1.💾 O(N) to store elements in the set.

Detailed Dry Run

Set	Checking	Found?
{1, 2, 0}	1	Yes
{1, 2, 0}	2	Yes
{1, 2, 0}	3	No! Result=3

java

import java.util.*;

public class Main {
    public static int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        for (int i = 1; i <= nums.length + 1; i++) {
            if (!set.contains(i)) return i;
        }
        return 1;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 0};
        System.out.println(firstMissingPositive(nums)); // Output: 3
    }
}

Approach 3

Level III: Optimal Solution (Cyclic Sort)

Intuition

Use the array itself as a 'hash map'. Since the answer must be in the range [1, N+1], try to place every number x in the range [1, N] at index x-1. For example, 1 should be at index 0, 2 at index 1, etc. After one pass of swapping, the first index i where nums[i] != i+1 gives the missing number.

⏱ O(N) - even with the `while` loop, each element is moved to its correct position at most once.💾 O(1) extra space as we reorder the input array.

Detailed Dry Run

Cyclic Sort Visualization

nums = [3, 4, -1, 1]

nums[0]=3: Swap with nums[2] -> [-1, 4, 3, 1]
nums[1]=4: Swap with nums[3] -> [-1, 1, 3, 4]
nums[1]=1: Swap with nums[0] -> [1, -1, 3, 4]
Done! nums[1] is -1, which is not 1+1=2. Answer: 2

java

public class Main {
    public static 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 temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums)); // Output: 2
    }
}

Insert Delete GetRandom O(1)

To achieve $O(1)$ average time for all operations, we combine a HashMap and an ArrayList. The ArrayList stores the values for $O(1)$ random access, while the HashMap stores value-to-index mappings for $O(1)$ lookups and deletions. Deletion is optimized by swapping the target element with the last element in the list.

Implement the RandomizedSet class: bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements. Each element must have the same probability of being returned. All operations must be O(1) average time complexity.

Visual Representation

Insert 10: Array=[10], Map={10: 0}
Insert 20: Array=[10, 20], Map={10: 0, 20: 1}
Remove 10:
1. Swap 10 with last (20): Array=[20, 10]
2. Update Map: {20: 0}
3. Pop last: Array=[20]

Medium

Examples

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]
RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Approach 1

Level I: Brute Force (ArrayList only)

Intuition

Use a simple dynamic array (ArrayList/vector) to store elements. For insert, we first check if the element exists by scanning the entire list, which takes O(N). For remove, we search for the element (O(N)) and then shift remaining elements (O(N)). For getRandom, we pick a random index in O(1). This approach fails the O(1) requirement for insert and remove.

⏱ O(N) for insert/remove, O(1) for getRandom💾 O(N) to store elements.

Detailed Dry Run

Action	List	Result
insert(1)	[1]	true
insert(1)	[1]	false (contains)
getRandom	[1]	1

java

import java.util.*;

public class RandomizedSet {
    private List<Integer> list;
    private Random random;
    public RandomizedSet() {
        list = new ArrayList<>();
        random = new Random();
    }
    public boolean insert(int val) {
        if (list.contains(val)) return false;
        list.add(val); return true;
    }
    public boolean remove(int val) {
        return list.remove(Integer.valueOf(val));
    }
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.remove(2)); // false
        System.out.println(rs.insert(2)); // true
        System.out.println(rs.getRandom()); // 1 or 2
    }
}

Approach 2

Level II: Better Solution (HashSet)

Intuition

A HashSet allows insert and remove operations in O(1) average time. However, sets do not support efficient random access by index. To implement getRandom, we must either iterate through the set or convert it to an array/list, both of which take O(N) time. This approach optimizes insert/remove but at the cost of a slow getRandom.

⏱ O(1) for insert/remove, O(N) for getRandom💾 O(N) to store unique elements.

Detailed Dry Run

Action	Set	Result
insert(1)	{1}	true
getRandom	list({1})	1 (Slow conversion)

java

import java.util.*;

public class RandomizedSet {
    private Set<Integer> set;
    private Random random;
    public RandomizedSet() {
        set = new HashSet<>();
        random = new Random();
    }
    public boolean insert(int val) { return set.add(val); }
    public boolean remove(int val) { return set.remove(val); }
    public int getRandom() {
        Integer[] arr = set.toArray(new Integer[0]); // O(N)
        return arr[random.nextInt(arr.length)];
    }
    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(1)); // true
        System.out.println(rs.getRandom()); // 1
    }
}

Approach 3

Level III: Optimal Solution (HashMap + Array)

Intuition

To achieve O(1) for all operations, we combine a HashMap and a dynamic array (List). The List stores elements for O(1) random access, and the HashMap stores value -> index mapping for O(1) lookup. The key trick is in remove: instead of shifting elements (O(N)), we swap the target element with the last element of the list, update its index in the map, and pop the last element in O(1).

⏱ O(1) average for all operations.💾 O(N) to store elements and their index mappings.

Detailed Dry Run

O(1) Removal Visualization

List: [10, 20, 30, 40]  Map: {10:0, 20:1, 30:2, 40:3}
Remove 20:
1. Find index of 20 (index = 1)
2. Get last element (40)
3. Set List[1] = 40, Update Map {40:1}
4. Pop last element from List, delete 20 from Map
Result: [10, 40, 30]  Map: {10:0, 40:1, 30:2}

java

import java.util.*;

public class RandomizedSet {
    private Map<Integer, Integer> map; // value -> index
    private List<Integer> list; // values
    private Random random;
    
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int lastElement = list.get(list.size() - 1);
        
        // Swap with last element
        list.set(index, lastElement);
        map.put(lastElement, index);
        
        // Remove last element
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

    public static void main(String[] args) {
        RandomizedSet rs = new RandomizedSet();
        System.out.println(rs.insert(10)); // true
        System.out.println(rs.insert(20)); // true
        System.out.println(rs.remove(10)); // true
        System.out.println(rs.getRandom()); // 20
    }
}

Count of Smaller Numbers After Self

Counting smaller elements to the right can be solved by iterating backwards and using a data structure that supports 'insert' and 'count elements smaller than X'. Candidates include Binary Indexed Trees (BIT), Segment Trees, or modifying Merge Sort to track displacements. The Merge Sort approach is highly efficient as it naturally counts how many times an element from the right half is moved before an element from the left half.

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Visual Representation

nums = [5, 2, 6, 1]

Right of 5: [2, 6, 1] -> 2 smaller (2, 1)
Right of 2: [6, 1]    -> 1 smaller (1)
Right of 6: [1]       -> 1 smaller (1)
Right of 1: []        -> 0 smaller

Result: [2, 1, 1, 0]

Hard

Examples

Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each element at index i, iterate through all elements to its right (index j > i) and count how many are smaller than nums[i]. This is the most straightforward approach but inefficient for large arrays.

⏱ O(N²) - two nested loops.💾 O(1) extra space (excluding the result array).

Detailed Dry Run

nums = [5, 2, 6, 1]

i=0, v=5: [2, 6, 1] -> 2, 1 are smaller. Count=2.
i=1, v=2: [6, 1] -> 1 is smaller. Count=1.
i=2, v=6: [1] -> 1 is smaller. Count=1.
i=3, v=1: [] -> Count=0. Result: [2, 1, 1, 0]

java

import java.util.*;

public class Main {
    public static List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) count++;
            }
            result.add(count);
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums)); // [2, 1, 1, 0]
    }
}

Approach 2

Level II: Better Solution (Binary Indexed Tree)

Intuition

Iterate through the array from right to left. For each element, we want to know how many elements we've already seen that are smaller than it. We can use a Binary Indexed Tree (BIT) to store the frequencies of the elements seen so far. Since the numbers can be large or negative, we use Coordinate Compression to map them to a small range [1, unique_elements].

⏱ O(N log N) - sorting for compression and BIT operations.💾 O(N) to store ranks and BIT.

Detailed Dry Run

BIT State Walkthrough

nums = [5, 2, 6, 1] -> Sorted Unique: [1, 2, 5, 6]
Ranks: {1:1, 2:2, 5:3, 6:4}

Backward Traversal:
1. val=1, rank=1: Query sum(0)=0. Update BIT at index 1.
2. val=6, rank=4: Query sum(3)=1. Update BIT at index 4.
3. val=2, rank=2: Query sum(1)=1. Update BIT at index 2.
4. val=5, rank=3: Query sum(2)=2. Update BIT at index 3.
Result: [2, 1, 1, 0]

java

import java.util.*;

public class Main {
    static int[] bit;
    private static void update(int i, int n) {
        for (; i <= n; i += i & -i) bit[i]++;
    }
    private static int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += bit[i];
        return sum;
    }
    
    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 1;
        for (int i = 0; i < n; i++) {
            if (i == 0 || sorted[i] != sorted[i-1]) rank.put(sorted[i], r++);
        }
        
        bit = new int[r];
        Integer[] res = new Integer[n];
        for (int i = n - 1; i >= 0; i--) {
            res[i] = query(rank.get(nums[i]) - 1);
            update(rank.get(nums[i]), r - 1);
        }
        return Arrays.asList(res);
    }
    
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums));
    }
}

Approach 3

Level III: Optimal Solution (Modified Merge Sort)

Intuition

This approach uses the property of Merge Sort: while merging two sorted halves left and right, if we pick an element from left, any elements already moved from right to the temporary array are smaller than the current element and were originally to its right. We track original indices to update the counts array correctly.

⏱ O(N log N) - standard Merge Sort complexity.💾 O(N) for indices and temporary arrays.

Detailed Dry Run

Merge Step Trace

Left: [5, 2] (Indices: [0, 1])
Right: [6, 1] (Indices: [2, 3])

During Merge [5, 2] and [6, 1]:
- 1 from Right is picked: Smaller count for elements in Left increases.
- 2 from Left is picked: Counts[1] += (number of elements already picked from Right).

java

import java.util.*;

public class Main {
    private static int[] counts;
    private static int[] indices;

    public static List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        indices = new int[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        
        mergeSort(nums, 0, n - 1);
        
        List<Integer> res = new ArrayList<>();
        for (int x : counts) res.add(x);
        return res;
    }

    private static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private static void merge(int[] nums, int left, int mid, int right) {
        int[] tempIndices = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0, rightCount = 0;

        while (i <= mid && j <= right) {
            if (nums[indices[j]] < nums[indices[i]]) {
                rightCount++;
                tempIndices[k++] = indices[j++];
            } else {
                counts[indices[i]] += rightCount;
                tempIndices[k++] = indices[i++];
            }
        }

        while (i <= mid) {
            counts[indices[i]] += rightCount;
            tempIndices[k++] = indices[i++];
        }
        while (j <= right) tempIndices[k++] = indices[j++];

        for (int p = 0; p < tempIndices.length; p++) indices[left + p] = tempIndices[p];
    }
    
    public static void main(String[] args) {
        int[] nums = {5, 2, 6, 1};
        System.out.println(countSmaller(nums)); // [2, 1, 1, 0]
    }
}

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Visual Representation

Box Index Formula: (row / 3) * 3 + (col / 3)

Row 0-2, Col 0-2 -> Box 0
Row 0-2, Col 3-5 -> Box 1
Row 3-5, Col 0-2 -> Box 3

Medium

Examples

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[.".","9","8",".",".",".",".","6","."]
...]
Output: true

Approach 1

Level I: Triple Pass

Intuition

Check rows, columns, and 3x3 boxes separately. For each check, use a boolean array or set to detect duplicates.

⏱ O(N²)💾 O(N)

Detailed Dry Run

Check Row 0: [5, 3, ., 7, .] -> Unique numbers. OK. Check Col 0: [5, 6, ., 8, 4...] -> Unique. OK.

java

import java.util.*;
class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i=0; i<9; i++) {
            Set<Character> row = new HashSet<>(), col = new HashSet<>(), box = new HashSet<>();
            for(int j=0; j<9; j++) {
                if(board[i][j] != '.' && !row.add(board[i][j])) return false;
                if(board[j][i] != '.' && !col.add(board[j][i])) return false;
                int r = 3*(i/3) + j/3, c = 3*(i%3) + j%3;
                if(board[r][c] != '.' && !box.add(board[r][c])) return false;
            }
        }
        return true;
    }
}

Approach 2

Level II: Single Pass with HashSets

Intuition

Iterate over the board once. Maintain arrays of HashSets for rows, columns, and boxes to track seen digits.

⏱ O(N²)💾 O(N²)

Detailed Dry Run

i=4, j=4, val='5'

Seen in row 4? No.
Seen in col 4? No.
Seen in box (4/3)*3 + 4/3 = 4? No. Store it.

java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                if (board[i][j] != '.') {
                    String b = "(" + board[i][j] + ")";
                    if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3)) return false;
                }
            }
        }
        return true;
    }
}

Approach 3

Level III: Bitmasking (Optimal Space)

Intuition

Use an integer (32-bit) as a bitmask for each row, column, and box. The $n$ -th bit represents the presence of digit $n$ .

⏱ O(N²)💾 O(N) - 27 integers total.

Detailed Dry Run

i=0, val='5'. mask = 1 << 5 (binary 00100000). Set bit in row[0], col[0], box[0].

java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9], cols = new int[9], boxes = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int val = board[i][j] - '1';
                int box_idx = (i / 3) * 3 + j / 3;
                if (((rows[i] >> val) & 1) == 1 || ((cols[j] >> val) & 1) == 1 || ((boxes[box_idx] >> val) & 1) == 1) return false;
                rows[i] |= (1 << val);
                cols[j] |= (1 << val);
                boxes[box_idx] |= (1 << val);
            }
        }
        return true;
    }
}

Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Visual Representation

Input: ["hello", "world"]

Encoding: length + '#' + string
"hello" -> "5#hello"
"world" -> "5#world"
Result: "5#hello5#world"

Decoding: Read length, skip '#', read N chars.

Medium

Examples

Input: ["hello", "world"]
Output: ["hello", "world"]

Approach 1

Level I: Simple Delimiter (Risk: Collision)

Intuition

Join strings with a semicolon or other delimiter. This fails if a string itself contains the delimiter.

⏱ O(N)💾 O(N)

Detailed Dry Run

["a;b", "c"] -> "a;b;c" -> Decodes to ["a", "b", "c"] (Error!)

java

public class Codec {
    public String encode(List<String> strs) {
        return String.join(";", strs);
    }
    public List<String> decode(String s) {
        return Arrays.asList(s.split(";", -1));
    }
}

Approach 2

Level II: Length + Separator (Standard)

Intuition

Prefix each string with its length followed by a special character (e.g., '#'). When decoding, read the length, skip '#' and take that many characters.

⏱ O(N)💾 O(N)

Detailed Dry Run

["leet", "code"] -> "4#leet4#code" Read 4, skip #, read 'leet'. Read 4, skip #, read 'code'.

java

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s.length()).append("#").append(s);
        return sb.toString();
    }
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') j++;
            int length = Integer.parseInt(s.substring(i, j));
            res.add(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return res;
    }
}

Approach 3

Level III: Optimal Solution (Base64 Encoding / Escaping)

Intuition

To handle any characters including delimiters and lengths, use an escaping mechanism or standard Base64 encoding. Alternatively, use a fixed-width length prefix (e.g., 4 bytes) for true binary safety.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: ["3#a", "b"] Encoding: Escape # as ##. Use # as delimiter. Result: "3##a#b#" Decoding: Unescape ## back to #.

java

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.replace("#", "##")).append(" # ");
        }
        return sb.toString();
    }
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        String[] parts = s.split(" # ", -1);
        for (int i=0; i<parts.length-1; i++) res.add(parts[i].replace("##", "#"));
        return res;
    }
}

Brick Wall

There is a rectangular brick wall in front of you. The wall is n rows high and the width is the same for each row. You want to draw a vertical line from the top to the bottom and cross the least number of bricks. Each row is represented by a list of brick widths. A line crosses a brick if it passes through its interior, but not its edge.

Visual Representation

Row 1: [1, 2, 2, 1] -> Edges at: 1, 3, 5
Row 2: [3, 1, 2]    -> Edges at: 3, 4

Frequency of Edges:
1: 1
3: 2 (Max! Draw line here)
5: 1
4: 1

Min bricks crossed = Total Rows - Max Edge Frequency

Medium

Examples

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Approach 1

Level I: Brute Force

Intuition

Check every possible vertical line position (at every 0.5 unit width up to total width). For each position, count how many bricks are crossed. Extremely slow.

⏱ O(N * Width)💾 O(1)

Detailed Dry Run

Width=6. Check 1, 2, 3, 4, 5. Line at 3: Row1 (edge), Row2 (edge)... Crosses 0 bricks in those rows.

java

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int width = 0; for(int b : wall.get(0)) width += b;
        int minBricks = wall.size();
        for(int pos=1; pos<width; pos++) {
            int crossed = 0;
            for(List<Integer> row : wall) {
                int edge = 0; boolean onEdge = false;
                for(int b : row) {
                    edge += b; if(edge == pos) { onEdge = true; break; }
                    if(edge > pos) break;
                }
                if(!onEdge) crossed++;
            }
            minBricks = Math.min(minBricks, crossed);
        }
        return minBricks;
    }
}

Approach 2

Level II: HashMap (Edge Frequency)

Intuition

A line crosses the least bricks if it passes through the most edges. We use a HashMap to count the frequency of edges (prefix sums) at each position (excluding the far right edge).

⏱ O(N) where N is the total number of bricks.💾 O(M) where M is the number of unique edge positions.

Detailed Dry Run

Row: [1, 2, 2, 1] -> Edges: {1:1, 3:1, 5:1} Row: [3, 1, 2] -> Edges: {1:1, 3:2, 5:1, 4:1} Max edges = 2 (at pos 3). Min bricks = Rows(2) - Max(2) = 0.

java

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> counts = new HashMap<>();
        int maxEdges = 0;
        for (List<Integer> row : wall) {
            int edge = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                edge += row.get(i);
                counts.put(edge, counts.getOrDefault(edge, 0) + 1);
                maxEdges = Math.max(maxEdges, counts.get(edge));
            }
        }
        return wall.size() - maxEdges;
    }
}

Approach 3

Level III: Optimal Solution (Pointer-based Merge)

Intuition

Similar to merging K sorted lists, we can treat each row's edges as a sorted list. Use pointers to advance through edges across all rows, counting occurrences at each position. This is more efficient if the number of bricks is massive but rows are few.

⏱ O(N log R) where N is total bricks and R is number of rows.💾 O(R) for pointers.

Detailed Dry Run

Row 1: [1, 2, 2, 1] -> Edges: [1, 3, 5] Row 2: [3, 1, 2] -> Edges: [3, 4] Initially: ptrs=[0, 0]. Curr Edges: [1, 3]. Min is 1. Pop 1. Next min is 3. Pop 3 from both. Count=2.

java

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < wall.size(); i++) {
            if (wall.get(i).size() > 1) pq.offer(new int[]{wall.get(i).get(0), i, 0});
        }
        int maxEdges = 0;
        while (!pq.isEmpty()) {
            int currPos = pq.peek()[0];
            int count = 0;
            while (!pq.isEmpty() && pq.peek()[0] == currPos) {
                int[] top = pq.poll();
                count++;
                int rowIdx = top[1], brickIdx = top[2];
                if (brickIdx + 1 < wall.get(rowIdx).size() - 1) {
                    pq.offer(new int[]{currPos + wall.get(rowIdx).get(brickIdx + 1), rowIdx, brickIdx + 1});
                }
            }
            maxEdges = Math.max(maxEdges, count);
        }
        return wall.size() - maxEdges;
    }
}

Isomorphic Strings

Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Visual Representation

s = "egg", t = "add"

e -> a
g -> d
Result: "add" (True)

s = "foo", t = "bar"
f -> b
o -> a
o -> r (Conflict! 'o' already mapped to 'a')

Easy

Examples

Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

Approach 1

Level I: Two HashMaps (Bidirectional)

Intuition

A character in s must map to exactly one character in t, and vice versa. We use two maps to ensure this 1-to-1 relationship.

⏱ O(N)💾 O(1) - alphabet size is finite.

Detailed Dry Run

s="ab", t="aa" m1: {a: a}, m2: {a: a} m1: {b: a}, m2 already has {a: a}! Conflict.

java

import java.util.*;
class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> m1 = new HashMap<>(), m2 = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if((m1.containsKey(c1) && m1.get(c1) != c2) || 
               (m2.containsKey(c2) && m2.get(c2) != c1)) return false;
            m1.put(c1, c2); m2.put(c2, c1);
        }
        return true;
    }
}

Approach 2

Level II: Last Seen Index (Space Optimized)

Intuition

Characters are isomorphic if they appear at the same relative indices throughout the string. We track the 'last seen' index for each character.

⏱ O(N)💾 O(1) - fixed size arrays.

Detailed Dry Run

s="egg", t="add" e(0), a(0) -> Match g(1), d(1) -> Match g(2), d(2) -> Match

java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256], m2 = new int[256];
        for(int i=0; i<s.length(); i++) {
            if(m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
            m1[s.charAt(i)] = i + 1; m2[t.charAt(i)] = i + 1;
        }
        return true;
    }
}

Approach 3

Level III: Optimal Solution (Canonical Form)

Intuition

Convert both strings to a 'canonical' or 'normal' form where each character is replaced by the index of its first appearance. If both strings produce the same normalized form, they are isomorphic.

⏱ O(N)💾 O(N)

Detailed Dry Run

s = "paper" -> First seen indices: p:0, a:1, e:3, r:4. Normalized: [0, 1, 0, 3, 4] t = "title" -> First seen indices: t:0, i:1, l:3, e:4. Normalized: [0, 1, 0, 3, 4] Match!

java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        return transform(s).equals(transform(t));
    }
    private String transform(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) map.put(s.charAt(i), i);
            sb.append(map.get(s.charAt(i))).append(",");
        }
        return sb.toString();
    }
}

Continuous Subarray Sum

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

Visual Representation

nums = [23, 2, 4, 6, 7], k = 6

Prefix Sum Modulo k:
- 23 % 6 = 5
- (23+2) % 6 = 25 % 6 = 1
- (25+4) % 6 = 29 % 6 = 5 (FOUND EXISTING REMAINDER!)

Subarray from index 1 to 2 has sum (2+4)=6 (multiple of 6).
Size = 2 (Valid)

Medium

Examples

Input: nums = [23,2,4,6,7], k = 6
Output: true

Approach 1

Level I: Brute Force (All Subarrays)

Intuition

Iterate through all possible subarrays and calculate their sum. If any sum is a multiple of k and length is $\ge 2$ , return true.

⏱ O(N²)💾 O(1)

Detailed Dry Run

i=0, j=1: sum=23+2=25 (Not multiple of 6) i=1, j=2: sum=2+4=6 (Multiple of 6!) return true

java

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }
}

Approach 2

Level II: Better Solution (Prefix Sum O(N²))

Intuition

Use a prefix sum array to calculate the sum of any subarray in O(1). Iterate through all pairs $(i, j)$ with $j-i \ge 1$ and check if $(prefix[j+1] - prefix[i]) \pmod k == 0$ .

⏱ O(N²)💾 O(N)

Detailed Dry Run

nums=[23, 2, 4], prefix=[0, 23, 25, 29] i=0, j=1: (25-0)%6 = 1 i=1, j=2: (29-23)%6 = 0 (Match!)

java

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = prefix[j+1] - prefix[i];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }
}

Approach 3

Level III: Prefix Sum + Modulo Hashing

Intuition

If the remainder of $(prefixSum[i] \pmod k)$ is the same as $(prefixSum[j] \pmod k)$ , then the subarray sum from $i+1$ to $j$ is a multiple of $k$ . We use a HashMap to store remainder -> first_seen_index and check if current_index - first_seen_index >= 2.

⏱ O(N)💾 O(min(N, k))

Detailed Dry Run

nums=[23, 2, 4], k=6. Map: {0: -1}

rem=5. Map: {0:-1, 5:0}
rem=(5+2)%6=1. Map: {0:-1, 5:0, 1:1}
rem=(1+4)%6=5. Key 5 exists at idx 0. Diff 2-0=2. return true.

java

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int rem = k == 0 ? sum : sum % k;
            if (map.containsKey(rem)) {
                if (i - map.get(rem) >= 2) return true;
            } else {
                map.put(rem, i);
            }
        }
        return false;
    }
}

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.