Arrays & Strings | Phase 2

What is an Array?

Arrays store elements in contiguous memory. The address of any element = base + index × sizeof(T). This gives O(1) random access — the most efficient read in computing.

[0]

[1]

[2]

[3]

[4]

[5]

arr[3] = 8 accessed in O(1) — jump directly, no scanning needed.

C++ tip: Use vector<int> for dynamic arrays. It wraps a heap-allocated array with automatic resizing (doubles when full → amortized O(1) push_back).

Operations & Complexity

Operation	Time	Space	Notes
arr[i] access	O(1)	O(1)	Direct address calculation
Linear search	O(n)	O(1)	Scan all elements
Binary search	O(log n)	O(1)	Requires sorted array
push_back	O(1)*	O(1)	Amortized — occasional resize
insert at index	O(n)	O(1)	Must shift all elements right
erase at index	O(n)	O(1)	Must shift all elements left

4 Essential Techniques

1. Two Pointers

left & right converge from opposite ends. Converts O(n²) pair searches to O(n). Core pattern for 3Sum, Trapping Rain Water.

2. Prefix Sum

prefix[i] = sum(arr[0..i−1]). Any range sum [l,r] in O(1): prefix[r+1] − prefix[l]. Build once, query many times.

3. Sliding Window

Window grows right, shrinks left when constraint broken. Solves all contiguous subarray/substring problems in O(n).

4. Kadane's Algorithm

Maximum subarray in O(n). At each step: extend previous or start fresh. cur = max(num, cur + num).

C++ Implementations

Prefix Sum — Range Queries in O(1)

C++

vector<int> buildPrefix(vector<int>& arr) {
    int n = arr.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

// Query sum of arr[l..r] in O(1) after O(n) build
int rangeSum(vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

// Example:
// arr    = {3, 1, 4, 1, 5, 9}
// prefix = {0, 3, 4, 8, 9, 14, 23}
// rangeSum(prefix, 1, 4) = 14 - 3 = 11  →  (1+4+1+5)
        

Kadane's Algorithm — Maximum Subarray

C++

int maxSubArray(vector<int>& nums) {
    int cur     = nums[0];
    int maxSum  = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        // Either extend the current subarray or start fresh here
        cur    = max(nums[i], cur + nums[i]);
        maxSum = max(maxSum, cur);
    }
    return maxSum;
}
// arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}  →  6  (subarray [4,-1,2,1])
// Time: O(n)   Space: O(1)
        

Two Pointers — Pair Sum in Sorted Array

C++

vector<int> twoSumSorted(vector<int>& arr, int target) {
    int l = 0;
    int r = arr.size() - 1;

    while (l < r) {
        int s = arr[l] + arr[r];
        if (s == target) {
            return {l, r};
        } else if (s < target) {
            l++;    // sum too small → move left pointer right
        } else {
            r--;    // sum too big  → move right pointer left
        }
    }
    return {};
}
// Time: O(n)   Space: O(1)
        

Interactive: Insert & Delete with Shifting

Watch how inserting or deleting at a mid-index forces O(n) element shifts — and why arrays pay a cost for mid-mutations.

Interactive: Two Pointers — Reverse In Place

lo and hi walk inward, swapping each pair. Only O(n/2) swaps needed, O(1) extra space.

Deeper Understanding

🧠 Under the Hood

All elements are contiguous in memory. The CPU can compute any element's address in a single multiply-and-add. The first 4 int elements fit in one cache line — iterating forwards is extremely cache-friendly, which is why arrays outperform linked lists for sequential reads even when they're the same O(n) complexity.

⚖️ When to Use / When NOT to Use

✅ Use when you need O(1) random access by index

No structure beats arrays for indexed reads — direct address math.

✅ Use when you iterate sequentially (sorting, scanning)

Cache locality makes array traversal 5–10× faster than pointer-chasing structures.

✅ Use when you only append to the end

vector push_back is amortized O(1) — the cheapest dynamic structure for tail-only appends.

❌ Avoid when you need frequent mid-inserts or mid-deletes

Instead: std::list (O(1) splice) or std::deque (O(1) front). Arrays pay O(n) per mid-op.

❌ Avoid when size is deeply unpredictable

Instead: std::deque avoids the occasional O(n) resize copy that vector incurs.

🚫 Common Misconceptions

❌ "vector.erase(it) is O(1)"

Erase at position i shifts all elements after i left — O(n). Only erase-at-end is O(1). Use swap-with-last then pop_back if order doesn't matter.

❌ "push_back is always O(1)"

Occasionally O(n) when the internal buffer doubles. Amortized O(1) over many pushes — but a single push_back can trigger a full copy.

❌ "Passing a vector copies it"

Pass by const ref (const vector<int>&) for reads, by ref (vector<int>&) for mutation. Pass by value only when you need a local copy.

🎤 Interview Follow-ups

Q: Explain amortized O(1) push_back.

When capacity is full, vector doubles (copies n elements). Over n pushes the total work is 1+2+4+…+n = 2n → O(1) per push on average.

Q: array vs vector vs deque — when would you pick each?

array: compile-time fixed size, stack-allocated. vector: dynamic, heap, O(1) push_back. deque: O(1) push both ends, segmented storage (not contiguous).

Q: Row-major vs column-major iteration cost?

In C++, 2D arrays are row-major. Iterating column-by-column causes a cache miss on every access (strides past a full row width). Always prefer row-major loops.

Q: When would you choose a linked list over a vector?

Only when you need O(1) insertion/deletion at an already-known node and you never need indexed access. In practice, vector wins due to cache performance.

Practice Problems

#1 Two Sum Easy ▼

Given nums and target, return indices of two numbers that add up to target. Exactly one solution guaranteed.

Pattern: Hash map stores num → index. For each num, check if (target − num) already exists in map.

C++

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;   // value → index

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];

        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}
// Time: O(n)   Space: O(n)
          

#121 Best Time to Buy and Sell Stock Easy ▼

Find the maximum profit from one buy-sell. You must buy before you sell.

Pattern: Track minimum price seen so far. At each price: profit = price − minPrice. Update maxProfit.

C++

int maxProfit(vector<int>& prices) {
    int minPrice  = INT_MAX;
    int maxProfit = 0;

    for (int price : prices) {
        minPrice  = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    return maxProfit;
}
// Time: O(n)   Space: O(1)
          

#238 Product of Array Except Self Medium ▼

Return output[i] = product of all elements except nums[i]. No division allowed. O(n) time, O(1) extra space.

Pattern: Two passes — first fill with left prefix products, then multiply by right suffix products in-place.

C++

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 1);

    // Left pass: res[i] holds product of nums[0..i-1]
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        res[i] = prefix;
        prefix *= nums[i];
    }

    // Right pass: multiply each position by product of nums[i+1..n-1]
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= suffix;
        suffix *= nums[i];
    }
    return res;
}
// Time: O(n)   Space: O(1)  (output array does not count)
          

#15 3Sum Medium ▼

Find all unique triplets [a, b, c] that sum to 0. No duplicate triplets in the result.

Pattern: Sort the array. Fix one element, use two pointers for the remaining pair. Skip duplicates at all three levels.

C++

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;

    for (int i = 0; i < (int)nums.size() - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;   // skip duplicate pivot
        }

        int l = i + 1;
        int r = nums.size() - 1;

        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];

            if (s == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l + 1]) l++;   // skip left dups
                while (l < r && nums[r] == nums[r - 1]) r--;   // skip right dups
                l++;
                r--;
            } else if (s < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return res;
}
// Time: O(n²)   Space: O(1)
          

#42 Trapping Rain Water Medium ▼

Given elevation heights, compute how much water is trapped after raining.

Pattern: Two pointers. Water at any cell = min(maxLeft, maxRight) − height. Process the side with the smaller max — it's the binding constraint.

C++

int trap(vector<int>& h) {
    int l     = 0;
    int r     = h.size() - 1;
    int lmax  = 0;
    int rmax  = 0;
    int water = 0;

    while (l < r) {
        if (h[l] <= h[r]) {
            lmax  = max(lmax, h[l]);
            water += lmax - h[l];
            l++;
        } else {
            rmax  = max(rmax, h[r]);
            water += rmax - h[r];
            r--;
        }
    }
    return water;
}
// Time: O(n)   Space: O(1)
          

#11 Container With Most Water Medium ▼

Find two lines forming a container with the most water. Area = width × min(h[l], h[r]).

Pattern: Two pointers. Always move the shorter side inward — moving the taller side can never increase area (width shrinks, height can't improve).

C++

int maxArea(vector<int>& h) {
    int l    = 0;
    int r    = h.size() - 1;
    int best = 0;

    while (l < r) {
        int area = min(h[l], h[r]) * (r - l);
        best = max(best, area);

        if (h[l] < h[r]) {
            l++;
        } else {
            r--;
        }
    }
    return best;
}
// Time: O(n)   Space: O(1)
          

#128 Longest Consecutive Sequence Medium ▼

Find the length of the longest consecutive sequence in an unsorted array. Must be O(n).

Pattern: Hash set for O(1) lookup. Only start counting from n where (n − 1) is NOT in the set — that identifies the true start of a sequence.

C++

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;

    for (int n : s) {
        if (!s.count(n - 1)) {      // n is the start of a sequence
            int cur = n;
            int len = 1;

            while (s.count(cur + 1)) {
                cur++;
                len++;
            }
            best = max(best, len);
        }
    }
    return best;
}
// Time: O(n)   Space: O(n)
          

#53 Maximum Subarray Easy ▼

Find the contiguous subarray with the largest sum. Classic Kadane's algorithm problem.

Pattern: At each position: extend current subarray OR start a new one. Local maximum feeds the global maximum.

C++

int maxSubArray(vector<int>& nums) {
    int cur  = nums[0];
    int best = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        cur  = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}
// Time: O(n)   Space: O(1)
          

#88 Merge Sorted Array Easy ▼

Merge nums2 into nums1 in-place. nums1 has extra space at the end. Both are sorted.

Pattern: Back-fill from the end using two pointers — avoids overwriting elements not yet processed.

C++

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0)
        nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
    while (j >= 0) nums1[k--] = nums2[j--]; // remaining nums2
}
// Time: O(m+n)   Space: O(1)
          

#169 Majority Element Easy ▼

Find the element that appears more than ⌊n/2⌋ times. Guaranteed to exist. O(1) space required.

Pattern: Boyer-Moore voting — maintain a candidate and a count. Non-matching elements cancel out the candidate; the survivor is the majority.

C++

int majorityElement(vector<int>& nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (count == 0) candidate = nums[i];
        count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;
}
// Time: O(n)   Space: O(1)  — majority guaranteed so no verification needed
          

#189 Rotate Array Medium ▼

Rotate array right by k steps in-place with O(1) extra space.

Pattern: Triple-reverse trick — reverse all, reverse [0,k−1], reverse [k,n−1]. Each reverse is O(n) and composition gives the rotation.

C++

void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;                                       // handle k > n
    reverse(nums.begin(), nums.end());            // reverse all
    reverse(nums.begin(), nums.begin() + k);      // reverse first k
    reverse(nums.begin() + k, nums.end());        // reverse rest
}
// Time: O(n)   Space: O(1)
          

#31 Next Permutation Medium ▼

Rearrange numbers into the next lexicographically greater permutation in-place with O(1) extra space.

Pattern: Find rightmost "descent" (nums[i] < nums[i+1]), swap with the smallest element to its right that is larger, then reverse the suffix.

C++

void nextPermutation(vector<int>& nums) {
    int n = nums.size(), i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;  // find descent
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;              // find swap target
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());       // reverse suffix
}
// Time: O(n)   Space: O(1)
          

#41 First Missing Positive Hard ▼

Find the smallest missing positive integer. Must be O(n) time and O(1) space.

Pattern: Use the array as a hash map — place each positive nums[i] at index nums[i]−1. Then scan for the first index where nums[i] ≠ i+1.

C++

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {             // cycle-sort: place nums[i] at index nums[i]-1
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i])
            swap(nums[i], nums[nums[i]-1]);
    }
    for (int i = 0; i < n; i++)
        if (nums[i] != i + 1) return i + 1;
    return n + 1;
}
// Time: O(n)   Space: O(1)  — each element moved at most once
          

Before coding, always ask: Is the array sorted? Are there duplicates? Can I use O(n) extra space? Do I need to handle negative numbers? These 4 questions often reveal which technique applies.