Array

6 problems using this pattern

About this pattern:

Fundamental data structure problems involving indexing, iteration, and manipulation.

Often used with: Two Pointers Dynamic Programming Hash Map Hash Set Prefix Sum

Complexity Range

Time Complexity

O(n) (6 problems)

Space Complexity

O(n) (2 problems)
O(1) (4 problems)

Problems Using Array

Two Sum

Given an array of integers and a target, return the indices of two numbers that add up to the target.

Easy LeetCode
Time:
O(n)?
Why O(n)?
Single pass through the array
We visit each element exactly once in the loop. For each element, hash lookup and insertion are O(1) operations.
Example: Array of 1000 elements = ~1000 operations
Space:
O(n)?
Why O(n)?
Hash map stores up to n elements
In the worst case, we might store almost every element in the hash map before finding the solution.
Example: Array [1,2,3,4] with target 7 stores 3 elements in hash
Example: nums = [2,7,11,15], target = 9 → [0,1]
Hash Map Array
View Solution →

Contains Duplicate

Returns true if the input array has any duplicates, false otherwise.

Easy LeetCode
Time: O(n)
Space: O(n)
Example: [1,2,3,1] → true
Hash Set Array
View Solution →

Product of Array Except Self

Returns a new array such that each index has the product of all elements except itself.

Medium LeetCode
Time: O(n)
Space: O(1)
Example: [1,2,3,4] → [24,12,8,6]
Array Prefix Sum
View Solution →

Two Sum II - Input Array Is Sorted

Find two numbers in sorted array that add up to target. Return 1-indexed positions.

Medium LeetCode
Time: O(n)
Space: O(1)
Example: [2,7,11,15], target=9 → [1,2]
Two Pointers Array
View Solution →

Trapping Rain Water

Calculate how much water can be trapped after raining given elevation heights.

Hard LeetCode
Time:
O(n)?
Why O(n)?
Single pass with two pointers moving towards center
We visit each element exactly once. Each position is processed when either left or right pointer reaches it.
Example: Array of 12 elements needs exactly 12 operations (6 from each pointer)
Space:
O(1)?
Why O(1)?
Only using a few variables regardless of input size
We only store left_max, right_max, and two pointers - constant space that doesn't grow with input.
Example: Same memory usage for array of 10 or 10,000 elements
Example: [0,1,0,2,1,0,1,3,2,1,2,1] → 6
Two Pointers Array
View Solution →

House Robber

Rob houses in a line, but can't rob adjacent houses. Find maximum money.

Medium LeetCode
Time: O(n)
Space: O(1)
Example: [2,7,9,3,1] → 12 (rob houses 0,2,4)
Dynamic Programming Array
View Solution →
← Back to All Patterns
View All Categories