Arrays Questions Placement
Arrays - Complete Placement Interview Question Bank
Last Updated: March 2026
Introduction: Why Arrays Matter in Coding Interviews
Arrays are the foundation of computer science and the most frequently asked data structure in technical interviews at companies like Google, Amazon, Microsoft, and Meta. An array is a contiguous block of memory that stores elements of the same data type, allowing O(1) access by index.
Arrays test your ability to:
- Think in terms of indices and boundaries
- Optimize space and time complexity
- Apply two-pointer, sliding window, and prefix-sum techniques
- Handle edge cases efficiently
Over 40% of all coding interview questions involve arrays or array-based problems, making them the #1 topic for interview preparation.
Key Concepts and Theory
1. Array Properties
- Contiguous Memory: All elements stored in consecutive memory locations
- Fixed Size (Static Arrays): Size determined at creation
- Dynamic Arrays: Vector (C++), ArrayList (Java), List (Python) - auto-resize
- 0-indexed vs 1-indexed: Most languages use 0-indexed
2. Common Operations & Complexities
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Access by index | O(1) | O(1) |
| Search (unsorted) | O(n) | O(1) |
| Search (sorted) | O(log n) - Binary Search | O(1) |
| Insert at end | O(1) amortized | O(1) |
| Insert at beginning/middle | O(n) | O(1) |
| Delete | O(n) | O(1) |
3. Essential Techniques
Two Pointers
- Opposite ends: One at start, one at end (moving towards each other)
- Same direction: Both moving forward at different speeds
- Use cases: Pair sum, palindrome check, removing duplicates
Sliding Window
- Fixed or variable-size subarray problems
- Use cases: Maximum sum subarray, longest substring without repeating characters
Prefix Sum
- Precompute cumulative sums for O(1) range queries
- Use cases: Range sum queries, subarray sum equals k
Dutch National Flag (Three-way partitioning)
- Sort array with 0s, 1s, and 2s in single pass
- Foundation for QuickSort's 3-way partition
Time/Space Complexity Cheat Sheet
┌─────────────────────────────────────────────────────────────┐
│ ARRAY OPERATIONS │
├─────────────────────────────────────────────────────────────┤
│ Traversal │ O(n) │ Visit every element │
│ Linear Search │ O(n) │ Unsorted data │
│ Binary Search │ O(log n)│ Sorted data only │
│ Two-pointer scan │ O(n) │ Sorted/unsorted │
│ Sorting │ O(n log n)│ Comparison-based sort │
│ Finding max/min │ O(n) │ Single pass required │
│ Reversing │ O(n) │ Two-pointer technique │
│ Rotating │ O(n) │ Reverse 3 times method │
└─────────────────────────────────────────────────────────────┘
Practice Questions with Solutions
Question 1: Two Sum (EASY ⭐)
Problem: Given an array of integers nums and an integer target, return indices of two numbers that add up to target.
Example: nums = [2,7,11,15], target = 9 → [0,1]
Solution:
def two_sum(nums, target):
"""
Hash Map approach - O(n) time, O(n) space
"""
seen = {} # value -> index mapping
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return [] # No solution found
# Alternative: Two-pointer for sorted array - O(n log n)
def two_sum_sorted(nums, target):
nums = sorted(enumerate(nums), key=lambda x: x[1]) # Sort with original indices
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left][1] + nums[right][1]
if current_sum == target:
return sorted([nums[left][0], nums[right][0]])
elif current_sum < target:
left += 1
else:
right -= 1
return []
Follow-up: Can you do it in O(n) time?
Question 2: Best Time to Buy and Sell Stock (EASY ⭐)
Problem: Given prices array where prices[i] is stock price on day i, maximize profit by choosing a single day to buy and different day to sell.
Solution:
def max_profit(prices):
"""
One-pass approach - O(n) time, O(1) space
Track minimum price seen so far and max profit
"""
if not prices or len(prices) < 2:
return 0
min_price = float('inf')
max_profit = 0
for price in prices:
# Update minimum price if current is lower
if price < min_price:
min_price = price
# Calculate profit if sold today
else:
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
Follow-up: What if you can make multiple transactions? (LeetCode 122)
Question 3: Contains Duplicate (EASY ⭐)
Problem: Given array, determine if any value appears at least twice.
Solution:
def contains_duplicate(nums):
"""
Set approach - O(n) time, O(n) space
"""
return len(nums) != len(set(nums))
# Without extra space (modifies array) - O(n log n) time, O(1) space
def contains_duplicate_no_space(nums):
nums.sort() # Sort in-place
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return True
return False
Question 4: Product of Array Except Self (MEDIUM ⭐⭐)
Problem: Given array, return array where each element is product of all other elements. Do it without division and in O(n).
Example: [1,2,3,4] → [24,12,8,6]
Solution:
def product_except_self(nums):
"""
Prefix and suffix products - O(n) time, O(1) space (excluding output)
Idea: result[i] = (product of all left elements) * (product of all right elements)
"""
n = len(nums)
result = [1] * n
# First pass: calculate prefix products (left to right)
# result[i] contains product of all elements to the left of i
for i in range(1, n):
result[i] = result[i-1] * nums[i-1]
# Second pass: calculate suffix products (right to left)
# Multiply result[i] by product of all elements to the right
right_product = 1
for i in range(n-1, -1, -1):
result[i] *= right_product
right_product *= nums[i]
return result
Time: O(n) | Space: O(1) excluding output array
Question 5: Maximum Subarray (Kadane's Algorithm) (MEDIUM ⭐⭐)
Problem: Find contiguous subarray with largest sum.
Solution:
def max_subarray(nums):
"""
Kadane's Algorithm - O(n) time, O(1) space
Core idea: At each position, decide whether to:
1. Start new subarray at current element, OR
2. Extend existing subarray by adding current element
"""
if not nums:
return 0
current_sum = max_sum = nums[0]
for num in nums[1:]:
# Either start fresh or extend
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# With start and end indices
def max_subarray_with_indices(nums):
if not nums:
return 0, 0, 0
current_sum = max_sum = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if current_sum + nums[i] < nums[i]:
current_sum = nums[i]
temp_start = i
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start = temp_start
end = i
return max_sum, start, end
Question 6: Find Minimum in Rotated Sorted Array (MEDIUM ⭐⭐)
Problem: Array was sorted then rotated. Find minimum element in O(log n).
Solution:
def find_min_rotated(nums):
"""
Modified Binary Search - O(log n) time, O(1) space
Key insight: In rotated sorted array, one half is always sorted.
Minimum is always in the unsorted half (or at pivot).
"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# Compare mid with right to determine which half contains minimum
if nums[mid] > nums[right]:
# Minimum must be in right half (after mid)
left = mid + 1
elif nums[mid] < nums[right]:
# nums[mid] could be minimum, or it's in left half
right = mid
else: # nums[mid] == nums[right]
# Can't determine, reduce search space
right -= 1
return nums[left]
Question 7: 3Sum (MEDIUM ⭐⭐)
Problem: Find all unique triplets that sum to zero.
Solution:
def three_sum(nums):
"""
Sort + Two Pointers - O(n²) time, O(1) extra space (excluding output)
"""
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
# Skip duplicates for first element
if i > 0 and nums[i] == nums[i-1]:
continue
# Two sum for remaining target
left, right = i + 1, n - 1
target = -nums[i]
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates
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 current_sum < target:
left += 1
else:
right -= 1
return result
Question 8: Container With Most Water (MEDIUM ⭐⭐)
Problem: Given heights array, find two lines that form container holding most water.
Solution:
def max_area(height):
"""
Two Pointers from ends - O(n) time, O(1) space
Key insight: The area is limited by the shorter line.
Move the pointer at the shorter line inward to potentially find taller line.
"""
left, right = 0, len(height) - 1
max_water = 0
while left < right:
# Calculate area
width = right - left
h = min(height[left], height[right])
max_water = max(max_water, width * h)
# Move pointer at shorter line
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
Question 9: Next Permutation (MEDIUM ⭐⭐)
Problem: Rearrange to next lexicographically greater permutation. If not possible, sort ascending.
Solution:
def next_permutation(nums):
"""
Three-step algorithm - O(n) time, O(1) space
1. Find first decreasing element from right (pivot)
2. Find smallest element greater than pivot to its right
3. Swap and reverse suffix
"""
n = len(nums)
# Step 1: Find pivot (first element smaller than its right)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# Step 2: Find successor and swap (if pivot exists)
if i >= 0:
j = n - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# Step 3: Reverse suffix starting at i+1
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
Question 10: Search in Rotated Sorted Array (MEDIUM ⭐⭐)
Problem: Search target in rotated sorted array in O(log n).
Solution:
def search_rotated(nums, target):
"""
Modified Binary Search - O(log n) time
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Determine which half is sorted
if nums[left] <= nums[mid]: # Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Question 11: Merge Intervals (MEDIUM ⭐⭐)
Problem: Merge all overlapping intervals.
Solution:
def merge_intervals(intervals):
"""
Sort + Single pass - O(n log n) time, O(n) space
"""
if not intervals:
return []
# Sort by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
# Check if overlaps
if current[0] <= last[1]: # Overlapping
last[1] = max(last[1], current[1]) # Merge
else:
merged.append(current)
return merged
Question 12: Find All Duplicates in Array (MEDIUM ⭐⭐)
Problem: Given array where 1 ≤ a[i] ≤ n, find all elements appearing twice. O(n) time, O(1) space.
Solution:
def find_duplicates(nums):
"""
In-place marking using index as hash key - O(n) time, O(1) space
Idea: Use sign of nums[abs(num)-1] to mark presence
"""
result = []
for num in nums:
index = abs(num) - 1
if nums[index] < 0: # Already negative, seen before
result.append(abs(num))
else:
nums[index] *= -1 # Mark as seen
return result
Question 13: Trapping Rain Water (HARD ⭐⭐⭐)
Problem: Given elevation map, compute trapped water after raining.
Solution:
def trap(height):
"""
Two-pointer optimal approach - O(n) time, O(1) space
Key insight: Water trapped at position depends on min(max_left, max_right) - height[i]
"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
# Process left side
if height[left] >= left_max:
left_max = height[left] # New left boundary
else:
water += left_max - height[left] # Trap water
left += 1
else:
# Process right side
if height[right] >= right_max:
right_max = height[right] # New right boundary
else:
water += right_max - height[right] # Trap water
right -= 1
return water
# Alternative: Dynamic Programming approach - O(n) time, O(n) space
def trap_dp(height):
if not height:
return 0
n = len(height)
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water
Question 14: First Missing Positive (HARD ⭐⭐⭐)
Problem: Find smallest missing positive integer in O(n) time, O(1) space.
Solution:
def first_missing_positive(nums):
"""
Index as hash key approach - O(n) time, O(1) space
Idea: Place number n at index n-1 (Cyclic sort variation)
"""
n = len(nums)
# Place each number in its correct position
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# Swap to correct position
correct_idx = nums[i] - 1
nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
# Find first position where index != value - 1
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
Question 15: Subarray Sum Equals K (MEDIUM ⭐⭐)
Problem: Count total continuous subarrays whose sum equals k.
Solution:
def subarray_sum(nums, k):
"""
Prefix Sum + Hash Map - O(n) time, O(n) space
Key insight: If prefix_sum[i] - prefix_sum[j] = k, then sum(j+1 to i) = k
"""
count = 0
current_sum = 0
prefix_sums = {0: 1} # Empty subarray has sum 0
for num in nums:
current_sum += num
# If (current_sum - k) exists, those subarrays sum to k
if current_sum - k in prefix_sums:
count += prefix_sums[current_sum - k]
# Update frequency of current prefix sum
prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1
return count
Question 16: Longest Consecutive Sequence (MEDIUM ⭐⭐)
Problem: Find length of longest consecutive elements sequence in O(n).
Solution:
def longest_consecutive(nums):
"""
Hash Set approach - O(n) time, O(n) space
Key insight: Only start counting from numbers that are sequence starts
(i.e., num-1 is not in set)
"""
if not nums:
return 0
num_set = set(nums)
longest = 0
for num in num_set:
# Only start if num is beginning of sequence
if num - 1 not in num_set:
current_num = num
current_streak = 1
# Count consecutive numbers
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest = max(longest, current_streak)
return longest
Question 17: Largest Rectangle in Histogram (HARD ⭐⭐⭐)
Problem: Find largest rectangle area in histogram.
Solution:
def largest_rectangle_area(heights):
"""
Monotonic Stack - O(n) time, O(n) space
Key insight: For each bar, find width where it's the minimum
"""
stack = [] # Stack of indices with increasing heights
max_area = 0
n = len(heights)
for i in range(n + 1):
# Use 0 as sentinel to pop remaining bars
current_height = heights[i] if i < n else 0
# Pop while current is smaller (can't extend further)
while stack and current_height < heights[stack[-1]]:
height = heights[stack.pop()]
# Width extends from previous smaller to next smaller (current)
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
Question 18: Sliding Window Maximum (HARD ⭐⭐⭐)
Problem: Given array and window size k, find max in each sliding window.
Solution:
from collections import deque
def max_sliding_window(nums, k):
"""
Monotonic Deque - O(n) time, O(k) space
Key insight: Deque stores indices of elements in decreasing order
Front always has max of current window
"""
result = []
dq = deque() # Store indices, values in decreasing order
for i, num in enumerate(nums):
# Remove elements out of current window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove smaller elements (they can't be max)
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# Start adding results once window is full
if i >= k - 1:
result.append(nums[dq[0]])
return result
Question 19: Median of Two Sorted Arrays (HARD ⭐⭐⭐)
Problem: Find median of two sorted arrays in O(log(min(m,n))).
Solution:
def find_median_sorted_arrays(nums1, nums2):
"""
Binary Search on partitions - O(log(min(m,n)))
Key insight: Partition both arrays such that left halves have equal elements
and all left elements <= all right elements
"""
# Ensure nums1 is smaller
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total_left = (m + n + 1) // 2 # Elements in left partition
left, right = 0, m
while left <= right:
# Partition nums1 at i, nums2 at j
i = (left + right) // 2
j = total_left - i
# Elements around partition
nums1_left = float('-inf') if i == 0 else nums1[i-1]
nums1_right = float('inf') if i == m else nums1[i]
nums2_left = float('-inf') if j == 0 else nums2[j-1]
nums2_right = float('inf') if j == n else nums2[j]
# Check if partition is correct
if nums1_left <= nums2_right and nums2_left <= nums1_right:
# Found correct partition
if (m + n) % 2 == 1:
return max(nums1_left, nums2_left)
else:
return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
elif nums1_left > nums2_right:
# Move partition in nums1 to left
right = i - 1
else:
# Move partition in nums1 to right
left = i + 1
Question 20: Jump Game II (MEDIUM ⭐⭐)
Problem: Given max jump length at each position, reach end in minimum jumps.
Solution:
def jump(nums):
"""
Greedy BFS approach - O(n) time, O(1) space
Track current jump's reach and next jump's maximum reach
"""
if len(nums) <= 1:
return 0
jumps = 0
current_end = 0 # Furthest we can reach with current jumps
furthest = 0 # Furthest we can reach with jumps+1
for i in range(len(nums) - 1): # Don't need to jump from last position
furthest = max(furthest, i + nums[i])
# When we reach end of current jump range
if i == current_end:
jumps += 1
current_end = furthest
# Early termination
if current_end >= len(nums) - 1:
break
return jumps
Common Interview Follow-up Questions
-
"Can you solve this in-place?"
- Tests space optimization skills
- Common for: Dutch National Flag, Move Zeros
-
"What if the array is sorted/rotated/streaming?"
- Tests adaptability to variations
- Binary search often becomes applicable
-
"How would you handle duplicates?"
- Edge case handling
- Skip duplicates in two-pointer approaches
-
"Can you do this with multiple threads?"
- Parallel processing considerations
- Partition array, process chunks, merge results
-
"What if the array doesn't fit in memory?"
- External sorting algorithms
- Streaming/chunked processing
Companies That Frequently Ask Arrays
| Company | Frequency | Common Questions |
|---|---|---|
| ⭐⭐⭐⭐⭐ | Product Except Self, Trapping Rain Water, Merge Intervals | |
| Amazon | ⭐⭐⭐⭐⭐ | Two Sum, Container With Water, Sliding Window Max |
| Microsoft | ⭐⭐⭐⭐ | 3Sum, Search Rotated Array, Subarray Sum K |
| Meta | ⭐⭐⭐⭐ | Move Zeros, Longest Consecutive, First Missing Positive |
| Apple | ⭐⭐⭐⭐ | Next Permutation, Median of Arrays, Largest Rectangle |
| Netflix | ⭐⭐⭐ | Trapping Rain Water, Jump Game, Maximum Subarray |
| Uber | ⭐⭐⭐ | Merge Intervals, Meeting Rooms, Insert Interval |
| Adobe | ⭐⭐⭐ | Container With Water, 3Sum, Find Duplicates |
Preparation Tips for Array Problems
-
Master the Fundamentals: Know binary search variations by heart - it's the foundation for many optimal solutions.
-
Learn Patterns, Not Problems: Focus on recognizing patterns (two-pointer, sliding window, prefix sum) rather than memorizing specific questions.
-
Practice Edge Cases: Empty arrays, single elements, all same elements, negative numbers, and integer overflow scenarios.
-
Start with Brute Force: Always explain brute force first, then optimize. This shows structured thinking.
-
Trace with Examples: Walk through your algorithm with a small example during the interview - it catches errors early.
-
Know Time-Space Tradeoffs: Be ready to discuss when O(n) space is acceptable vs. when O(1) is required.
-
Mock Interviews: Practice verbalizing your thought process. Array problems are often about clear communication.
Frequently Asked Questions (FAQ)
Q1: Should I always sort the array first?
A: Not always. Sorting takes O(n log n). If you can solve in O(n) with hash maps or two pointers on unsorted data, that's often better. Sort when the problem explicitly requires it or enables a significantly cleaner solution.
Q2: How do I choose between hash map and two-pointer approaches?
A: Use hash maps when you need O(1) lookups and O(n) space is acceptable. Use two pointers when the array is sorted or when space must be O(1). Two-pointer often has better cache performance.
Q3: What's the most common mistake in binary search on rotated arrays?
A: Incorrectly determining which half is sorted. Always check nums[left] <= nums[mid] to identify the sorted half, then check if target lies in that range.
Q4: How do I handle integer overflow in array problems?
A: Use Python (arbitrary precision) when possible. In languages like Java/C++, use left + (right - left) // 2 instead of (left + right) // 2 for mid calculation. Consider using long for sum calculations.
Q5: Can I modify the input array during the interview?
A: Always ask first! Some interviewers want in-place solutions (modification allowed), others want the original array preserved. If modifying, clarify that you're doing so and mention space complexity implications.
Quick Reference: Array Techniques
┌────────────────────────────────────────────────────────────────┐
│ TECHNIQUE │ WHEN TO USE │
├────────────────────────────────────────────────────────────────┤
│ Two Pointers │ Sorted arrays, pair problems, palindromes │
│ Sliding Window │ Subarray/substring problems │
│ Prefix Sum │ Range queries, subarray sum problems │
│ Binary Search │ Sorted/rotated arrays, search problems │
│ Cyclic Sort │ Numbers in range [1, n] │
│ Dutch National Flag │ Three-way partitioning │
│ Kadane's Algorithm │ Maximum subarray problems │
│ Monotonic Stack │ Next greater/smaller element │
│ Mo's Algorithm │ Range query problems (offline) │
└────────────────────────────────────────────────────────────────┘
Happy Coding! Practice consistently and you'll master arrays. ⚡