35 problems per part. 6 parts. 210 problems total — all from LeetCode, Codeforces, HackerRank and CodeChef. Every problem is fully decoded, approached, dry-run traced, and solved with annotated C++ code. This is Part 1: Arrays, Strings, Two Pointers, Sliding Window.
EASY — Should be solved in 10–15 min. If taking longer, you need more fundamentals.
MED — 20–35 min. The bulk of real interviews. This is where preparation shows.
HARD — 35–60 min. FAANG-level. Requires combining multiple patterns.
Orange box = Decode: strip the problem to its algorithmic core
Blue box = Approach: structured thinking before any code
Dashed trace = Dry Run: the algorithm animated on a real example
Code block = Annotated C++ solution
Read the problem. Close the book. Spend 10–20 minutes attempting it on paper or in an editor. THEN look at the Decode and Approach boxes. Still stuck? Read the trace. Only then look at the code. Copy-pasting solutions builds zero problem-solving muscle.
Given array nums and integer target, return the indices of the two numbers that add up to target. Exactly one solution exists. Same element can't be used twice.
nums=[2,7,11,15]
target=9[0,1]nums=[3,2,4]
target=6[1,2]For each number x at position i, you need to know: does (target − x) exist somewhere in the array before or after i? This is a lookup problem — not a search problem. The word "indices" tells you to remember positions, not just values. The moment you frame it as a lookup, the hash map appears.
For every i, loop j from i+1 to end. Check if nums[i]+nums[j]==target.
Walk array once. At each x, check if (target−x) is already in the map. If yes → answer. Else store x's index and move on.
Key mental model: Don't look for pairs. Instead, at each element x, ask: "is my complement (target−x) already stored?" If yes — you have your pair. If no — store x so future elements can use it as their complement. This turns the O(n²) "check every pair" into O(n) "store and check in one pass."
Critical detail: Look up BEFORE inserting. If you insert first, nums[0]+nums[0] could incorrectly match itself.
Array prices[i] = stock price on day i. Choose one day to buy and a later day to sell. Return the maximum profit. Return 0 if no profit is possible.
[7,1,5,3,6,4]5Buy day2(1)
Sell day5(6) → 5[7,6,4,3,1]0For each day, the best possible profit = today's price minus the cheapest price ever seen before today. You don't need to know the future — just track the minimum so far and compute the profit at each step.
Walk left to right. minPrice = cheapest day seen so far (update when you see something cheaper). maxProfit = best profit seen so far (update when today's price - minPrice is larger). No need to track which days — just the values.
Find the contiguous subarray with the largest sum and return its sum.
[-2,1,-3,4,-1,2,1,-5,4]6[4,-1,2,1] = 6At every index i, you have exactly two choices: extend the current subarray (add nums[i] to running sum) OR start fresh at nums[i]. You should start fresh whenever the running sum is negative — because a negative prefix can only drag down future sums. The key DP insight: curSum = max(nums[i], curSum + nums[i]).
Two variables: curSum (best ending at current position) and maxSum (global best seen so far). At each step, either extend or restart. Update global max. This is O(1) space DP — the "previous state" is just one number.
Edge case: Initialize both with nums[0], not 0. The subarray must contain at least one element, so an all-negative array should return its maximum (least negative) element.
Return array answer where answer[i] = product of all elements except nums[i]. Solve in O(n) without using division.
[1,2,3,4][24,12,8,6]ans[0]=2×3×4=24
ans[2]=1×2×4=8answer[i] = (product of all to LEFT of i) × (product of all to RIGHT of i). Build left products in one forward pass, then multiply by right products in one backward pass. No extra array for right products — accumulate in a single variable.
Find the contiguous subarray with the largest product and return that product.
[2,3,-2,4]6[-2,0,-1]0Unlike sum, a negative product can become positive when multiplied by another negative. So the current minimum (most negative) is just as important as the current maximum — a new negative could make it the new maximum. Track both curMax and curMin at all times. When you hit a negative number, swap them before computing.
Array of n integers, each in range [1,n]. Some appear twice, others once. Find all that appear twice. Must run in O(n) time with O(1) extra space.
[4,3,2,7,8,2,3,1][2,3]Since values are in [1,n], value v maps to index (v−1). When you "visit" value v, negate nums[v−1]. If you encounter v again and nums[v−1] is already negative, v has been seen twice → it's a duplicate. After processing, restore signs if needed.
Given an elevation map (heights array), compute how much water can be trapped after raining.
[0,1,0,2,1,0,1,3,2,1,2,1]6Water sits at position i up to the level of the shorter wall on either side. If that level is higher than h[i], water collects. The formula: water[i] = max(0, min(maxLeft[i], maxRight[i]) - h[i]). The challenge is computing maxLeft and maxRight efficiently.
For each i, scan left for max and right for max. O(n) per element.
Precompute leftMax[i] and rightMax[i] arrays. Then sum contributions in one pass.
Process from both ends. The shorter side's max is the bottleneck — compute its water, advance that pointer.
Two pointers lo (left) and hi (right). Track maxL and maxR (max heights seen from each side). At each step: if h[lo] < h[hi], the left side is the bottleneck. If h[lo] >= maxL, update maxL (no water here, it's a wall). Else water = maxL - h[lo]. Advance lo. Symmetrically for the right side.
Array of heights. Find two lines forming a container that holds the most water. Return the max area. Area = min(h[l], h[r]) × (r − l).
[1,8,6,2,5,4,8,3,7]49h[1]=8, h[8]=7
min(8,7)×7 = 49If we have pointers at l and r, the area is limited by the shorter wall. Moving the taller pointer inward: the width decreases, and the height is still bounded by the same or smaller value — area can only decrease or stay same. Moving the shorter pointer inward is the only way to possibly find a taller pair and improve area.
Find all unique triplets in the array that sum to zero. Answer must not contain duplicate triplets.
[-1,0,1,2,-1,-4][[-1,-1,2],
[-1,0,1]]Sort first. Fix nums[i] as the first element. Use two pointers j=i+1 and k=end to find pairs summing to −nums[i]. Sort enables both two pointers AND easy duplicate skipping (skip if nums[i]==nums[i-1]).
Outer loop fixes nums[i]. Skip duplicates at i. Inner: two pointers j and k from both sides of the remaining array. If sum==0: record, skip duplicates on both j and k sides. If sum<0: j++ (need larger). If sum>0: k-- (need smaller). Total: O(n²) with O(1) extra space.
Rotate array to the right by k positions in-place with O(1) extra space.
[1,2,3,4,5,6,7]
k=3[5,6,7,1,2,3,4]Right rotate by k: reverse entire array → reverse [0..k-1] → reverse [k..n-1]. Works because reversing strategically re-arranges elements in exactly the rotated order. Always take k = k % n first to handle k > n.
Check if a string is a palindrome considering only alphanumeric characters and ignoring case. "A man, a plan, a canal: Panama" → true.
Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercased characters. If any mismatch → false.
Return the longest palindromic substring of string s.
"babad""bab" or "aba""cbbd""bb"Every palindrome is symmetric about its center. There are 2n−1 possible centers (n single characters + n−1 gaps between characters). For each center, expand outward while characters match. Track the longest found. O(n²) time, O(1) space — better than O(n²) space DP.
For each index i, expand for odd-length palindromes (center at i) and even-length palindromes (center between i and i+1). Return the substring of the longest expansion found.
Design encode and decode functions to serialize a list of strings to a single string and back. Must handle any character including # and /.
["hello","world"]
→ "5#hello5#world""5#hello5#world"
→ ["hello","world"]You can't use a fixed delimiter like '|' because strings might contain it. Instead, prefix each string with its length followed by a separator character (like '#'). During decode, read the number, skip the '#', read exactly that many characters. Works for any content.
Given two sorted arrays of size m and n, return the median of the combined sorted array. Runtime must be O(log(min(m,n))).
A=[1,3], B=[2]2.0A=[1,2], B=[3,4]2.5The median divides the combined sorted array in half. We need to find where to cut both arrays such that: every element on the left half ≤ every element on the right half. Binary search on the partition point in the shorter array — the other partition is determined automatically.
Always binary search on A (the shorter array). Partition A at position i, B at position j=(m+n+1)/2−i. Check: A[i-1] ≤ B[j] AND B[j-1] ≤ A[i]. If A[i-1] > B[j]: move i left. If B[j-1] > A[i]: move i right. When correct: if (m+n) is odd → max(left halves). If even → average of (max left, min right).
Two Pointer (sorted array / opposite ends): When you need to find pairs/triplets. Works because sorted order lets you make greedy pointer movements — if sum is too small, move left pointer right; if too large, move right pointer left.
Sliding Window (same direction): When you need a contiguous subarray/substring satisfying some condition. Fixed window: add right element, remove left element each step. Variable window: expand until invalid, shrink until valid again.
Find the length of the longest substring without repeating characters.
"abcabcbb"3 ("abc")"pwwkew"3 ("wke")Maintain a window [left, right]. Expand right freely. When a duplicate is found, advance left past the PREVIOUS occurrence of that character. Use a hash map to store the LAST seen position of each character — this lets you jump left in one step instead of inching forward.
Return the minimum window substring of s that contains all characters of t (including duplicates). Return "" if no such window.
s="ADOBECODEBANC"
t="ABC""BANC"Track how many characters of t have been "satisfied" in the current window. Expand right until all are satisfied (window is valid). Then shrink left to find the smallest valid window. Record the best. When shrinking makes it invalid, expand right again. The key counter: formed = number of unique characters in t whose frequency in window matches the requirement.
need map: frequency of each char in t. have map: frequency of each char in current window. formed: incremented when have[c] == need[c] for some c. When formed == required (all t's unique chars satisfied), the window is valid — try to shrink left.
Find the maximum sum of any contiguous subarray of exactly size K.
[2,1,5,1,3,2], K=39 (5+1+3)Build the first window of K elements. Then for each new element added (right), remove the element that left the window (left = right - K). This is the "fixed window" sliding pattern — no variable shrinking needed.
Given string s and integer k, find the length of the longest substring containing the same letter that can be obtained by replacing at most k characters.
s="AABABBA", k=14"AABA" → replace B → "AAAA"The number of replacements needed to make the entire window one character = window size − frequency of the most common character. If this is ≤ k, the window is valid. Maximize the window size while keeping this condition true.
maxF is a monotone value — once it increases, it never needs to go lower for our purpose. If shrinking the window decreases the max frequency, the window size also decreases, so the condition can't get worse than before. We only care about windows LARGER than the current best, and those require maxF to increase.
Return true if s2 contains a permutation of s1 as a substring (i.e., some window in s2 is an anagram of s1).
s1="ab", s2="eidbaooo"true ("ba" in s2)A permutation of s1 in s2 = any window of length |s1| in s2 that has the same character frequencies as s1. Use two frequency arrays, maintain a matches counter (how many characters have matching frequencies). Update matches as you slide.
Return the maximum of each sliding window of size k as it slides across the array.
[1,3,-1,-3,5,3,6,7]
k=3[3,3,5,5,6,7]Brute force: for each window, scan k elements. O(nk). Better: use a monotonic decreasing deque — it stores candidate maximums in decreasing order. The front is always the current window's maximum. Elements that can never be the maximum (smaller elements behind a larger one) are discarded. Each element enters and exits the deque once → O(n).
Given integer array and integer k, count the total number of subarrays whose sum equals k. Array may contain negative numbers.
[1,1,1], k=22[1,1](0..1) and
[1,1](1..2)Rearranged: we want to count positions j where prefixSum[j] = prefixSum[i] - k. Keep a frequency map of prefix sums seen so far. At each position i, add freq[prefixSum - k] to the answer, then increment freq[prefixSum]. Note: negative numbers make sliding window INVALID here — must use prefix sum approach.
Find the length of the longest consecutive sequence in an unsorted array. Required: O(n) time.
[100,4,200,1,3,2]4 (1,2,3,4)An element n is the START of a sequence only if (n−1) is NOT in the set. Only then count consecutive elements from n. This avoids redundant counting — every element is visited at most twice total, giving O(n).
Return true if t is an anagram of s (same characters, same frequencies, any order).
s="anagram"
t="nagaram"trues="rat"
t="car"falseGiven an array of strings, group the anagrams together.
["eat","tea","tan","ate","nat","bat"][["bat"],["nat","tan"],["ate","eat","tea"]]"eat", "tea", "ate" all sort to "aet". Use the sorted form as the hash map key. All words with the same key belong to the same group.
Return the k most frequent elements. Answer can be in any order.
[1,1,1,2,2,3], k=2[1,2]Count frequencies. Create n+1 buckets where bucket[i] holds all elements with frequency i. Scan from the highest bucket downward, collecting elements until k are gathered. Total O(n) time — no sorting needed.
Count the number of contiguous subarrays where the product of all elements is strictly less than k. All nums[i] are positive.
[10,5,2,6], k=1008For a valid window ending at right, the new subarrays added are: [right], [right-1,right], ..., [left,right]. That's exactly (right − left + 1) subarrays. Shrink window when product ≥ k. Positive numbers mean the product is monotone as the window grows.
Find the longest subarray containing at most 2 distinct values. This is the general "at most K distinct" sliding window template (K=2 here).
[1,2,1,2,3]4 ([1,2,1,2])Given positive integers array and target, find the minimum length of a subarray whose sum is ≥ target. Return 0 if impossible.
[2,3,1,2,4,3], target=72 ([4,3])Expand right to increase sum. When sum ≥ target, the window is valid — record its length, then shrink left to see if a shorter window also satisfies. Since all values are positive, shrinking decreases the sum, so we can always know when to stop.
T1 — Exact match: lo≤hi, mid=(lo+hi)/2. Return index or -1.
T2 — First position where condition is true (lower_bound): lo=0, hi=n, lo<hi. If cond(mid): hi=mid. Else: lo=mid+1. Returns first valid index.
T3 — Last position where condition is true: lo=0, hi=n, lo<hi. If cond(mid): lo=mid+1. Else: hi=mid. Returns lo-1 = last valid.
T4 — Search on Answer Space: lo=min_answer, hi=max_answer. Binary search on the answer, verify with a helper function in O(n).
Given sorted array of distinct integers and target, return its index or -1 in O(log n).
Never write (lo+hi)/2 — it overflows for large indices. Always write lo + (hi-lo)/2. This is the single most common binary search bug.
Search for target in a rotated sorted array in O(log n).
[4,5,6,7,0,1,2]
target=04After a rotation, if we split at mid, either [lo..mid] or [mid..hi] is sorted. Check which half is sorted, then determine which half the target falls in, discard the other. This preserves O(log n) by eliminating half the search space each step.
Find the minimum element in a rotated sorted array of unique integers in O(log n).
[3,4,5,1,2]1If a[mid] > a[hi], the rotation point (minimum) is in the right half → lo = mid+1. Otherwise, minimum is in the left half including mid → hi = mid. When lo == hi, we have the minimum.
Koko eats bananas at speed k bananas/hr (at most). Each pile must be finished before moving to the next. Find the minimum k to finish all piles within h hours.
piles=[3,6,7,11]
h=84If speed k works, speed k+1 also works. This monotone property means: the feasible speeds form a contiguous range [minK, ∞). Binary search the boundary. Range: [1, max(piles)]. For each candidate k, check if all piles can be finished in ≤ h hours using ⌈pile/k⌉ for each pile.
Whenever you see "find the MINIMUM/MAXIMUM value such that some condition holds", suspect binary search on answer. The condition must be monotone: if it holds for x, it holds for all x' beyond x. Define the feasibility check function, then binary search the answer space [lo, hi].
Find the index of a peak element (greater than both neighbors). Array may have multiple peaks. Return any. O(log n) required.
[1,2,3,1]2If a[mid] < a[mid+1], the right side is "uphill" → there must be a peak somewhere to the right. Move lo = mid+1. If a[mid] > a[mid+1], the left side has a peak → hi = mid. This always converges to a peak in O(log n).
Design a time-based key-value store with set(key, value, timestamp) and get(key, timestamp) — returns the value with the largest timestamp ≤ given timestamp, or "" if none.
Timestamps are always increasing (given in the problem). For each key, store all (timestamp, value) pairs in sorted order. For get, binary search for the largest timestamp ≤ query timestamp (floor query = upper_bound - 1 pattern).
Split array into k non-empty subarrays to minimize the maximum subarray sum. Return that minimum possible maximum.
[7,2,5,10,8], k=218[7,2,5] and [10,8]
max=18, best possibleInstead of "find the optimal split" (hard), flip it: "given a maximum sum limit cap, can we split into ≤ k groups?" (easy greedy check). Monotone property: if cap works, cap+1 also works. Binary search on cap from [max(arr), sum(arr)].
Walk left to right. Greedily pack each element into the current group as long as the sum doesn't exceed cap. When it would exceed, start a new group. Count groups needed. If groups ≤ k → cap works.