Arrays

Master contiguous memory indexing, multi-language solutions, and interview concepts.

Select Set:

Static Array: Allocated on stack/heap with fixed size at compile/runtime. Size cannot be altered after declaration.

Dynamic Array (e.g., C++ std::vector, Java ArrayList): Automatically resizes when full. Usually doubles its capacity (Geometric Growth) to maintain an amortized O(1) insertion time complexity.

Arrays store elements in contiguous memory locations. The address of index i is calculated directly using a mathematical formula:

Address = Base_Address + (Index * Element_Size)

Because arithmetic calculation takes constant time regardless of array length, lookup is O(1).

Arrays exhibit high Spatial Locality. Because elements lie next to each other in RAM, loading one element loads adjacent elements into CPU L1/L2 caches simultaneously. Linked list nodes are scattered across RAM, causing frequent CPU cache misses.

Difficulty Set:

Easy

1. Two Sum

Solve on LeetCode

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Solution:

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); i++) {
        int diff = target - nums[i];
        if (mp.count(diff)) return {mp[diff], i};
        mp[nums[i]] = i;
    }
    return {};
}

import java.util.HashMap;

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (map.containsKey(diff)) {
            return new int[] { map.get(diff), i };
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

Medium

2. Maximum Subarray (Kadane's Algorithm)

Solve on LeetCode

Find the contiguous subarray with the largest sum and return its sum.

Solution:

int maxSubArray(vector<int>& nums) {
    int maxSoFar = nums[0], current = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        current = max(nums[i], current + nums[i]);
        maxSoFar = max(maxSoFar, current);
    }
    return maxSoFar;
}

public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0], current = nums[0];
    for (int i = 1; i < nums.length; i++) {
        current = Math.max(nums[i], current + nums[i]);
        maxSoFar = Math.max(maxSoFar, current);
    }
    return maxSoFar;
}

def maxSubArray(nums: list[int]) -> int:
    max_so_far = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        max_so_far = max(max_so_far, current)
    return max_so_far

Notes Set:

Array Operations Complete Guide.pdf

PDF Document

Download

Time Complexity Matrix

Access: O(1)
Search (Unsorted): O(n)
Insertion/Deletion (Middle): O(n)

Quiz Set:

Q1: What happens during Vector reallocation in C++?

New memory block is allocated, existing elements copied over, old memory freed. Memory is expanded in-place without copying.

Q2: What is the worst-case space complexity of Kadane's Algorithm?

O(1) Auxiliary Space O(N) Space