DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Solve 15 classic array interview problems that appear at top tech companies. Each problem includes the problem statement, multiple approaches from brute force to optimal, step-by-step solution explanation, complete code, and time/space complexity analysis.
Introduction
This lesson covers 15 classic array problems that appear repeatedly in technical interviews at companies like Google, Amazon, Microsoft, Meta, and Flipkart. For each problem, you will see the full thought process — from the brute force approach to the optimal solution — along with complete code and complexity analysis.
Work through each problem on your own before reading the solution. The struggle is where learning happens.
Problem 2 — Maximum Subarray (Kadane's Algorithm)
Problem: Find the contiguous subarray with the largest sum.
Example
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (subarray [4, -1, 2, 1])
Approach 1 — Brute Force: O(n²)
Check every possible subarray, keep track of maximum sum.
Approach 2 — Kadane's Algorithm: O(n) Time, O(1) Space
Key insight: At each position, decide whether to extend the current subarray or start fresh.
Example
def max_subarray(nums):
"""
Kadane's Algorithm: O(n) time, O(1) space.
max_ending_here = best sum ending at current position
max_so_far = best sum seen anywhere so far
"""
max_ending_here = nums[0]
max_so_far = nums[0]
for i in range(1, len(nums)):
# Either extend the previous subarray or start a new one at nums[i]
max_ending_here = max(nums[i], max_ending_here + nums[i])
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(max_subarray([-1, -2, -3])) # -1 (all negative)
Extended version — return the subarray itself:
Example
def max_subarray_with_indices(nums):
max_ending_here = nums[0]
max_so_far = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > max_ending_here + nums[i]:
max_ending_here = nums[i]
temp_start = i
else:
max_ending_here = max_ending_here + nums[i]
if max_ending_here > max_so_far:
max_so_far = max_ending_here
start = temp_start
end = i
return max_so_far, nums[start:end+1]
print(max_subarray_with_indices([-2,1,-3,4,-1,2,1,-5,4]))
# (6, [4, -1, 2, 1])
Time: O(n), Space: O(1)
Problem 3 — Best Time to Buy and Sell Stock
Problem: Given an array where prices[i] is the price on day i, find the maximum profit from one buy-sell transaction.
Example
Input: [7, 1, 5, 3, 6, 4]
Output: 5 (buy at 1, sell at 6)
Example
def max_profit(prices):
"""
Track minimum price seen so far.
For each day, profit = current_price - min_price_so_far.
Time: O(n), Space: O(1)
"""
if not prices:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0 (prices only decrease)
Time: O(n), Space: O(1)
Problem 4 — Product of Array Except Self
Problem: Return an array where output[i] = product of all elements except nums[i]. Do NOT use division. O(n) time.
Example
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Example
def product_except_self(nums):
"""
Two-pass approach: prefix products and suffix products.
Time: O(n), Space: O(1) [output array not counted]
Pass 1 (left to right): result[i] = product of all elements to the LEFT of i
Pass 2 (right to left): multiply result[i] by product of all elements to the RIGHT of i
"""
n = len(nums)
result = [1] * n
# Pass 1: result[i] = product of nums[0..i-1]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# result after pass 1: [1, 1, 2, 6]
# (result[0]=1, result[1]=nums[0]=1, result[2]=nums[0]*nums[1]=2, etc.)
# Pass 2: multiply by suffix product nums[i+1..n-1]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]
print(product_except_self([2, 3])) # [3, 2]
Time: O(n), Space: O(1) auxiliary
Problem 5 — Trapping Rain Water
Problem: Given heights of walls, compute how much water can be trapped after raining.
Example
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Visual:
Example
#
# ## #
# ## ### ##
0,1,0,2,1,0,1,3,2,1,2,1
Approach 1 — Precompute Max Left and Right: O(n) Time, O(n) Space
Example
def trap_water_arrays(heights):
n = len(heights)
left_max = [0] * n # max height to the left of i (inclusive)
right_max = [0] * n # max height to the right of i (inclusive)
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
right_max[n-1] = heights[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], heights[i])
water = 0
for i in range(n):
# Water level at i = min(max_left, max_right) - height[i]
water += min(left_max[i], right_max[i]) - heights[i]
return water
Approach 2 — Two Pointers: O(n) Time, O(1) Space
Example
def trap_water(heights):
"""
Two-pointer approach: move the pointer with the smaller max inward.
Time: O(n), Space: O(1)
"""
left, right = 0, len(heights) - 1
left_max = right_max = 0
water = 0
while left < right:
if heights[left] < heights[right]:
if heights[left] >= left_max:
left_max = heights[left]
else:
water += left_max - heights[left]
left += 1
else:
if heights[right] >= right_max:
right_max = heights[right]
else:
water += right_max - heights[right]
right -= 1
return water
print(trap_water([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap_water([4,2,0,3,2,5])) # 9
Time: O(n), Space: O(1)
Problem 6 — Merge Intervals
Problem: Given a collection of intervals, merge all overlapping intervals.
Example
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Example
def merge_intervals(intervals):
"""
Sort by start time, then merge overlapping intervals.
Time: O(n log n), Space: O(n)
"""
if not intervals:
return []
# Sort by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
# If current interval overlaps with the last merged interval
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # Extend if needed
else:
merged.append([start, end]) # No overlap — add new interval
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] — touching intervals are merged
Time: O(n log n), Space: O(n)
Problem 7 — Find Duplicate Number
Problem: Given an array of n+1 integers where each integer is in [1, n], find the duplicate. Only one duplicate exists.
Example
Input: [1, 3, 4, 2, 2]
Output: 2
Approach 1 — Sort: O(n log n)
Approach 2 — Hash Set: O(n) time, O(n) space
Approach 3 — Floyd's Cycle Detection: O(n) time, O(1) space
Example
def find_duplicate(nums):
"""
Treat array as a linked list where nums[i] is the next node.
A duplicate means two nodes point to the same next → cycle.
Time: O(n), Space: O(1)
"""
# Phase 1: Detect cycle
slow = fast = nums[0]
while True:
slow = nums[slow] # Move 1 step
fast = nums[nums[fast]] # Move 2 steps
if slow == fast:
break
# Phase 2: Find entry point of cycle (the duplicate)
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
print(find_duplicate([1,3,4,2,2])) # 2
print(find_duplicate([3,1,3,4,2])) # 3
Time: O(n), Space: O(1)
Problem 8 — Move Zeros to End
Problem: Move all zeros to the end of the array while maintaining relative order of non-zero elements. Do it in-place.
Example
Input: [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Example
def move_zeros(nums):
"""
Two-pointer: write_pos tracks where next non-zero goes.
Time: O(n), Space: O(1)
"""
write_pos = 0 # Position for next non-zero element
# Pass 1: Write all non-zero elements to the front
for num in nums:
if num != 0:
nums[write_pos] = num
write_pos += 1
# Pass 2: Fill remaining positions with zeros
while write_pos < len(nums):
nums[write_pos] = 0
write_pos += 1
return nums
print(move_zeros([0, 1, 0, 3, 12])) # [1, 3, 12, 0, 0]
print(move_zeros([0, 0, 1])) # [1, 0, 0]
Time: O(n), Space: O(1)
Problem 9 — 3Sum
Problem: Find all unique triplets that sum to zero.
Example
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1,-1,2],[-1,0,1]]
Example
def three_sum(nums):
"""
Sort + two pointers for each fixed element.
Time: O(n²), Space: O(1) auxiliary
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates for second and third elements
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
print(three_sum([-1,0,1,2,-1,-4])) # [[-1,-1,2],[-1,0,1]]
print(three_sum([0,0,0])) # [[0,0,0]]
Time: O(n²), Space: O(1)
Problem 10 — Jump Game
Problem: Given an array where nums[i] represents max jump length from position i, determine if you can reach the last index.
Example
Input: [2,3,1,1,4] → True
Input: [3,2,1,0,4] → False (stuck at 0)
Example
def can_jump(nums):
"""
Greedy: track the furthest position reachable.
Time: O(n), Space: O(1)
"""
max_reach = 0 # Furthest index reachable so far
for i in range(len(nums)):
if i > max_reach:
return False # Cannot reach index i
max_reach = max(max_reach, i + nums[i])
return True
print(can_jump([2,3,1,1,4])) # True
print(can_jump([3,2,1,0,4])) # False
Time: O(n), Space: O(1)
Problem 11 — Find Missing Number
Problem: Given an array of n distinct numbers in range [0, n], find the missing one.
Example
Input: [3,0,1] → 2
Input: [9,6,4,2,3,5,7,0,1] → 8
Example
def missing_number(nums):
"""
Sum formula: expected sum of [0..n] = n*(n+1)/2
Missing = expected - actual sum
Time: O(n), Space: O(1)
"""
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)
# Alternative using XOR
def missing_number_xor(nums):
"""XOR approach: XOR all indices and all values, missing one remains."""
result = len(nums)
for i, num in enumerate(nums):
result ^= i ^ num
return result
print(missing_number([3,0,1])) # 2
print(missing_number([9,6,4,2,3,5,7,0,1])) # 8
Time: O(n), Space: O(1)
Problem 12 — Sort Colors (Dutch National Flag)
Problem: Given array with only 0s, 1s, and 2s, sort it in-place in one pass.
Example
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example
def sort_colors(nums):
"""
Dutch National Flag Algorithm: three pointers.
low: boundary for 0s (everything before is 0)
mid: current element being processed
high: boundary for 2s (everything after is 2)
Time: O(n), Space: O(1), One pass
"""
low = mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# Don't increment mid — need to check the swapped element
return nums
print(sort_colors([2,0,2,1,1,0])) # [0,0,1,1,2,2]
print(sort_colors([2,0,1])) # [0,1,2]
Time: O(n), Space: O(1), Single pass
Problem 13 — Next Permutation
Problem: Find the next lexicographically greater permutation of numbers.
| Input: [1,2,3] | [1,3,2] |
| Input: [3,2,1] | [1,2,3] (wrap around to smallest) |
| Input: [1,1,5] | [1,5,1] |
Example
def next_permutation(nums):
"""
Algorithm:
1. Find rightmost position i where nums[i] < nums[i+1] (descending suffix)
2. Find smallest number in suffix that is > nums[i]
3. Swap them
4. Reverse the suffix
Time: O(n), Space: O(1)
"""
n = len(nums)
# Step 1: Find rightmost descent
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# Step 2: If found, find successor in suffix and swap
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# Step 3: Reverse the suffix (from i+1 to end)
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
print(next_permutation([1,2,3])) # [1,3,2]
print(next_permutation([3,2,1])) # [1,2,3]
print(next_permutation([1,1,5])) # [1,5,1]
Time: O(n), Space: O(1)
Problem 14 — Majority Element
Problem: Find the element that appears more than n/2 times. Guaranteed to exist.
Example
Input: [3,2,3] → 3
Input: [2,2,1,1,1,2,2] → 2
Example
def majority_element(nums):
"""
Boyer-Moore Voting Algorithm.
Time: O(n), Space: O(1)
Key insight: The majority element cancels all other elements.
If count drops to 0, the current candidate cannot be the majority.
"""
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num # New candidate
count += 1 if num == candidate else -1
return candidate
print(majority_element([3,2,3])) # 3
print(majority_element([2,2,1,1,1,2,2])) # 2
Time: O(n), Space: O(1)
Problem 15 — Subarray Sum Equals K
Problem: Count the number of subarrays that sum to exactly k.
Example
Input: nums = [1,1,1], k = 2
Output: 2 ([1,1] at indices [0,1] and [1,2])
Example
def subarray_sum(nums, k):
"""
Prefix sum + Hash Map.
prefix_sum[i] - prefix_sum[j] = k → prefix_sum[j] = prefix_sum[i] - k
For each prefix sum, check if (prefix_sum - k) was seen before.
Time: O(n), Space: O(n)
"""
count = 0
prefix_sum = 0
seen = {0: 1} # {prefix_sum: count of times seen}
for num in nums:
prefix_sum += num
# If (prefix_sum - k) was seen before, those subarrays sum to k
if prefix_sum - k in seen:
count += seen[prefix_sum - k]
seen[prefix_sum] = seen.get(prefix_sum, 0) + 1
return count
print(subarray_sum([1,1,1], 2)) # 2
print(subarray_sum([1,2,3], 3)) # 2 ([1,2] and [3])
print(subarray_sum([1,-1,1], 1)) # 3
Time: O(n), Space: O(n)
Problem Difficulty and Pattern Summary
| # | Problem | Pattern | Time | Space |
|---|---|---|---|---|
| 1 | Two Sum | Hash Map | O(n) | O(n) |
| 2 | Maximum Subarray | Kadane's DP | O(n) | O(1) |
| 3 | Buy and Sell Stock | Running minimum | O(n) | O(1) |
| 4 | Product Except Self | Prefix/suffix product | O(n) | O(1) |
| 5 | Trapping Rain Water | Two pointers | O(n) | O(1) |
| 6 | Merge Intervals | Sort + merge | O(n log n) | O(n) |
| 7 | Find Duplicate | Floyd's cycle | O(n) | O(1) |
| 8 | Move Zeros | Two pointers | O(n) | O(1) |
| 9 | 3Sum | Sort + two pointers | O(n²) | O(1) |
| 10 | Jump Game | Greedy | O(n) | O(1) |
| 11 | Missing Number | Math / XOR | O(n) | O(1) |
| 12 | Sort Colors | Dutch National Flag | O(n) | O(1) |
| 13 | Next Permutation | In-place manipulation | O(n) | O(1) |
| 14 | Majority Element | Boyer-Moore Voting | O(n) | O(1) |
| 15 | Subarray Sum = K | Prefix sum + HashMap | O(n) | O(n) |
Summary
These 15 problems cover the most important array patterns:
- Hash Map for O(1) lookup: Two Sum, Subarray Sum = K
- Two Pointers: 3Sum, Trapping Rain Water, Move Zeros, Sort Colors
- Prefix/Suffix Products: Product Except Self
- Greedy: Jump Game, Best Time to Buy Stock
- Kadane's Algorithm: Maximum Subarray
- Sorting + Merging: Merge Intervals
- Mathematical Tricks: Missing Number (sum formula / XOR)
- Voting Algorithm: Majority Element
- Cycle Detection: Find Duplicate
Master these patterns and the underlying reasoning — not just the solutions. In interviews, you will encounter variations of these exact problems.
*Arrays folder complete. Next Section: Linked Lists — The first pointer-based data structure, the foundation of all dynamic data structures.*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Array Interview Problems — 15 Classic Problems with Complete Solutions.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, arrays, array, interview
Related Data Structures & Algorithms Topics
Continue learning this concept
ArraysArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesA complete deep-dive into every array operation: traversal, insertion, deletion, searching, updating, sorting, merging, and rotating — with Python and Java implementations, time and space complexity for each, and important edge cases to handle.ArraysArray Rotation — Algorithms, Techniques, and Interview ProblemsMaster array rotation completely — left and right rotation, three different algorithms (brute force, cyclic replacement, reversal method), their time and space complexities, circular array problems, and classic interview problems based on rotation.ArraysArray Searching — Linear Search, Binary Search, and Advanced TechniquesComplete guide to searching arrays — linear search with early termination, binary search with all variants, interpolation search, and exponential search. Includes full implementations, complexity analysis, and classic search-based interview problems.ArraysArrays — The Complete Introduction to the Most Fundamental Data StructureA thorough introduction to arrays — what they are, how they work in memory, their properties, all basic operations with time and space complexity, comparison with other structures, and when to use them. The foundation of all data structure knowledge.ArraysDynamic Arrays — How Python Lists and ArrayLists Work InternallyUnderstand dynamic arrays from the ground up — how automatic resizing works, why append is O(1) amortized, how Python lists and Java ArrayLists are implemented, amortized analysis with the potential method, and how to implement your own dynamic array from scratch.ArraysMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutA complete guide to multidimensional arrays — how 2D and 3D arrays are stored in memory, row-major vs column-major order, all matrix operations with code and complexity, common matrix algorithms, and interview problems involving matrices.