{"title":"Introduction to Arrays","description":null,"content":"\n[![YouTube Video](https://img.youtube.com/vi/SlNq09scdWE/0.jpg)](https://www.youtube.com/watch?v=SlNq09scdWE)\n\n\nArrays are one of the most **fundamental data structures** in computer science. They are the building block and form the foundation for many other data structures and algorithms.\n\nArrays appear in basic loops and sorting, in standard library list types, and in advanced interview techniques like **two pointers**, **sliding window**, and **dynamic programming**.\n\nIn this chapter, I'll break down:\n\n- What an array is and how it works\n- What are dynamic arrays\n- Common array operations and their time complexities\n- The most popular interview patterns that use arrays\n\n---\n\n# What is an Array?\n\nAn **array** is a data structure used to store a **collection of elements of the same type**, arranged in a **contiguous block of memory**.\n\n#### **Integer array:**\n\n\n\n\n#### **Boolean array:**\n\n\n\n\n#### **String array:**\n\n\n\n\nTo store 100 numbers, creating separate variables like `num1, num2, ..., num100` would be impossible to manage.\n\nInstead, you store them in one structure:\n\nNow you can access any value using an **index**: `arr[0]`, `arr[1]`, `arr[2]`, ...\n\nMost programming languages use **zero-based indexing**, so the first element is at index `0`.\n\nAccessing an element in an array is fast because elements are stored **next to each other in memory.**\n\nWe can compute the address of any index using simple math:\n\n`address of arr[i] = base address + (i × size of each element)`\n\nThis allows you to retrieve any element in **constant time, O(1),** no matter how large the array is.\n\nBut arrays aren't perfect.\n\nIn languages like **C++** and **Java**, arrays have a **fixed size**. Once you allocate memory for 100 elements, you can't expand it.\n\nIf you need more space, you'll have to create a new, larger array and copy the data over, which takes **O(n)** time.\n\nMost programming languages provide a dynamic array type that resizes automatically as elements are added:\n\n- **Python** -> `list`\n- **Java** -> `ArrayList`\n- **C++** -> `vector`\n\nInternally, dynamic arrays **allocate more memory than needed**. For example, if you insert 5 elements, the underlying buffer might have space for 8 or 10.\n\n\n\n\n\nThis way, the array doesn't need to resize for every insertion.\n\nWhen the array runs out of space, it typically **doubles** its capacity, allocating a bigger chunk of memory, and **copying all elements** from the old array to the new one.\n\nThis operation is expensive, it takes **O(n)** time.\n\nBut because it doesn't happen often, the average time for inserting at the end remains **O(1).**\n\n---\n\n# Common Array operations\n\nThe most common array operations are accessing by index, traversal, insertion, deletion, and search. Each has a well-known time complexity:\n\n### 1. Accessing by Index\n\nSince the elements are stored in **contiguous memory layout,** the address of any element can be calculated directly using a simple formula.\n\n\n```java\nclass ArrayAccessExample {\n public static void main(String[] args) {\n int[] arr = {10, 20, 30, 40, 50};\n\n // Access element at index 2 (3rd element)\n int index = 2;\n int value = arr[index];\n\n System.out.println(\"Element at index \" + index + \" = \" + value);\n }\n}\n```\n\n```python\nclass ArrayAccessExample:\n @staticmethod\n def main():\n arr = [10, 20, 30, 40, 50]\n \n # Access element at index 2 (3rd element)\n index = 2\n value = arr[index]\n \n print(f\"Element at index {index} = {value}\")\n\nif __name__ == \"__main__\":\n ArrayAccessExample.main()\n```\n\n```cpp\n#include \nusing namespace std;\n\nclass ArrayAccessExample {\npublic:\n static void main() {\n int arr[] = {10, 20, 30, 40, 50};\n \n // Access element at index 2 (3rd element)\n int index = 2;\n int value = arr[index];\n \n cout << \"Element at index \" << index << \" = \" << value << endl;\n }\n};\n\nint main() {\n ArrayAccessExample::main();\n return 0;\n}\n```\n\n```csharp\nusing System;\n\npublic class ArrayAccessExample {\n public static void Main(string[] args) {\n int[] arr = {10, 20, 30, 40, 50};\n \n // Access element at index 2 (3rd element)\n int index = 2;\n int value = arr[index];\n \n Console.WriteLine($\"Element at index {index} = {value}\");\n }\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\ntype ArrayAccessExample struct{}\n\nfunc (a *ArrayAccessExample) Main() {\n arr := []int{10, 20, 30, 40, 50}\n \n // Access element at index 2 (3rd element)\n index := 2\n value := arr[index]\n \n fmt.Printf(\"Element at index %d = %d\\n\", index, value)\n}\n\nfunc main() {\n example := &ArrayAccessExample{}\n example.Main()\n}\n```\n\n```rust\nstruct ArrayAccessExample;\n\nimpl ArrayAccessExample {\n pub fn main() {\n let arr = [10, 20, 30, 40, 50];\n\n // Access element at index 2 (3rd element)\n let index = 2;\n let value = arr[index];\n\n println!(\"Element at index {} = {}\", index, value);\n }\n}\n\nfn main() {\n ArrayAccessExample::main();\n}\n```\n\n```javascript\nclass ArrayAccessExample {\n static main() {\n const arr = [10, 20, 30, 40, 50];\n \n // Access element at index 2 (3rd element)\n const index = 2;\n const value = arr[index];\n \n console.log(`Element at index ${index} = ${value}`);\n }\n}\n\nArrayAccessExample.main();\n```\n\n```typescript\nclass ArrayAccessExample {\n static main(): void {\n const arr: number[] = [10, 20, 30, 40, 50];\n \n // Access element at index 2 (3rd element)\n const index: number = 2;\n const value: number = arr[index];\n \n console.log(`Element at index ${index} = ${value}`);\n }\n}\n\nArrayAccessExample.main();\n```\n\n\nAs a result, accessing an element by index always takes constant time, whether the array has 10 elements or 10 million.\n\n### 2. Traversal\n\nTraversal means going through the array, one element at a time, commonly used for printing values, calculating a sum, or searching for a specific item.\n\n\n```java\nclass ArrayTraversalExample {\n public static void main(String[] args) {\n int[] arr = {3, 5, 7, 9, 11};\n\n // Traversal: visit each element exactly once\n System.out.print(\"Array elements: \");\n for (int i = 0; i < arr.length; i++) {\n System.out.print(arr[i] + \" \");\n }\n }\n}\n```\n\n```python\nclass ArrayTraversalExample:\n @staticmethod\n def main():\n arr = [3, 5, 7, 9, 11]\n \n # Traversal: visit each element exactly once\n print(\"Array elements: \", end=\"\")\n for i in range(len(arr)):\n print(arr[i], end=\" \")\n print()\n\nif __name__ == \"__main__\":\n ArrayTraversalExample.main()\n```\n\n```cpp\n#include \nusing namespace std;\n\nclass ArrayTraversalExample {\npublic:\n static void main() {\n int arr[] = {3, 5, 7, 9, 11};\n int length = 5;\n \n // Traversal: visit each element exactly once\n cout << \"Array elements: \";\n for (int i = 0; i < length; i++) {\n cout << arr[i] << \" \";\n }\n cout << endl;\n }\n};\n\nint main() {\n ArrayTraversalExample::main();\n return 0;\n}\n```\n\n```csharp\nusing System;\n\npublic class ArrayTraversalExample {\n public static void Main(string[] args) {\n int[] arr = {3, 5, 7, 9, 11};\n \n // Traversal: visit each element exactly once\n Console.Write(\"Array elements: \");\n for (int i = 0; i < arr.Length; i++) {\n Console.Write(arr[i] + \" \");\n }\n Console.WriteLine();\n }\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\ntype ArrayTraversalExample struct{}\n\nfunc (a *ArrayTraversalExample) Main() {\n arr := []int{3, 5, 7, 9, 11}\n \n // Traversal: visit each element exactly once\n fmt.Print(\"Array elements: \")\n for i := 0; i < len(arr); i++ {\n fmt.Print(arr[i], \" \")\n }\n fmt.Println()\n}\n\nfunc main() {\n example := &ArrayTraversalExample{}\n example.Main()\n}\n```\n\n```rust\nstruct ArrayTraversalExample;\n\nimpl ArrayTraversalExample {\n pub fn main() {\n let arr = [3, 5, 7, 9, 11];\n \n // Traversal: visit each element exactly once\n print!(\"Array elements: \");\n for i in 0..arr.len() {\n print!(\"{} \", arr[i]);\n }\n println!();\n }\n}\n\nfn main() {\n ArrayTraversalExample::main();\n}\n```\n\n```javascript\nclass ArrayTraversalExample {\n static main() {\n const arr = [3, 5, 7, 9, 11];\n \n // Traversal: visit each element exactly once\n process.stdout.write(\"Array elements: \");\n for (let i = 0; i < arr.length; i++) {\n process.stdout.write(arr[i] + \" \");\n }\n console.log();\n }\n}\n\nArrayTraversalExample.main();\n```\n\n```typescript\nclass ArrayTraversalExample {\n static main(): void {\n const arr: number[] = [3, 5, 7, 9, 11];\n \n // Traversal: visit each element exactly once\n process.stdout.write(\"Array elements: \");\n for (let i = 0; i < arr.length; i++) {\n process.stdout.write(arr[i] + \" \");\n }\n console.log();\n }\n}\n\nArrayTraversalExample.main();\n```\n\n\nSince each element is visited exactly once, this takes **O(n)** time, where `n` is the number of elements in the array.\n\n### 3. Insertion\n\nThe performance of insertion depends entirely on *where* the new element is placed.\n\nIf you insert at the end, it's fast. Place the element at the next index when there is free capacity.\n\nThis takes **amortized O(1)** time in dynamic arrays. Most appends are O(1), but the occasional resize copies every element, which costs O(n). Averaged over many insertions, the cost works out to O(1) per insertion.\n\nIf you insert at the beginning or the middle, it gets slower since all elements after the insertion point must be **shifted one position to the right** to make space. This shifting requires **O(n)** time in the worst case.\n\nEven though languages like Python (`list`) or Java (`ArrayList`) handle the shifting internally, the time complexity does not change, it still costs **O(n)** for inserting anywhere except the end.\n\n### 4. Deletion\n\nRemoving an element is similar to insertion, it depends on the position.\n\nIf you drop the last element, no shifting is required. It takes **O(1)** time.\n\nBut if you delete from start or middle, you'll need to **shift all following elements left** to fill the gap. That takes **O(n)** time.\n\nSo deleting the first element in a 1,000-element array means 999 elements need to move one step left.\n\n### 5. Search\n\nThe performance of searching depends heavily on whether the array is sorted.\n\nIf the array is **unsorted**, you'll have to scan through each element one by one which takes O(n) time.\n\nBut if the array is **sorted**, you can use **Binary Search**, which divides the search space in half with each step, reducing the time to **O(log n)**.\n\n---\n\n# Common Array Interview Patterns\n\nArrays show up in most coding interview questions, not as raw \"loop and print\" exercises but through a small set of well-known **problem-solving patterns**.\n\nHere are the most common array patterns you should know.\n\n### 1. Two Pointer Technique\n\nThe two-pointer pattern works on **sorted arrays** (or any array where the data has some ordered structure) by keeping two indices that move toward each other based on a comparison. One pointer starts at the left end, the other at the right end. At each step we compare the values at the two pointers and decide which pointer to advance.\n\nThe visualization below shows the two pointers narrowing the search range step by step:\n\n\n\n\nHere `left` advances twice while `right` stays, and then `right` retreats. Each move shrinks the candidate range without revisiting positions, which is what gives the pattern its **O(n)** behavior even though the array is being scanned from both directions.\n\nA classic application is **Two Sum on a sorted array**: find two indices whose values sum to a target.\n\n\n```java\nint[] twoSum(int[] nums, int target) {\n int left = 0, right = nums.length - 1;\n while (left < right) {\n int sum = nums[left] + nums[right];\n if (sum == target) return new int[]{left, right};\n if (sum < target) left++; // need a larger value\n else right--; // need a smaller value\n }\n return new int[]{-1, -1};\n}\n```\n\n```python\ndef two_sum(nums, target):\n left, right = 0, len(nums) - 1\n while left < right:\n s = nums[left] + nums[right]\n if s == target:\n return [left, right]\n if s < target:\n left += 1 # need a larger value\n else:\n right -= 1 # need a smaller value\n return [-1, -1]\n```\n\n```cpp\nstd::vector twoSum(std::vector& nums, int target) {\n int left = 0, right = nums.size() - 1;\n while (left < right) {\n int sum = nums[left] + nums[right];\n if (sum == target) return {left, right};\n if (sum < target) left++; // need a larger value\n else right--; // need a smaller value\n }\n return {-1, -1};\n}\n```\n\n```csharp\npublic int[] TwoSum(int[] nums, int target) {\n int left = 0, right = nums.Length - 1;\n while (left < right) {\n int sum = nums[left] + nums[right];\n if (sum == target) return new int[]{left, right};\n if (sum < target) left++; // need a larger value\n else right--; // need a smaller value\n }\n return new int[]{-1, -1};\n}\n```\n\n```go\nfunc twoSum(nums []int, target int) []int {\n left, right := 0, len(nums)-1\n for left < right {\n sum := nums[left] + nums[right]\n if sum == target {\n return []int{left, right}\n }\n if sum < target {\n left++ // need a larger value\n } else {\n right-- // need a smaller value\n }\n }\n return []int{-1, -1}\n}\n```\n\n```rust\npub fn two_sum(nums: &[i32], target: i32) -> Vec {\n let (mut left, mut right) = (0i32, nums.len() as i32 - 1);\n while left < right {\n let sum = nums[left as usize] + nums[right as usize];\n if sum == target {\n return vec![left, right];\n }\n if sum < target {\n left += 1; // need a larger value\n } else {\n right -= 1; // need a smaller value\n }\n }\n vec![-1, -1]\n}\n```\n\n```javascript\nfunction twoSum(nums, target) {\n let left = 0, right = nums.length - 1;\n while (left < right) {\n const sum = nums[left] + nums[right];\n if (sum === target) return [left, right];\n if (sum < target) left++; // need a larger value\n else right--; // need a smaller value\n }\n return [-1, -1];\n}\n```\n\n```typescript\nfunction twoSum(nums: number[], target: number): number[] {\n let left = 0, right = nums.length - 1;\n while (left < right) {\n const sum = nums[left] + nums[right];\n if (sum === target) return [left, right];\n if (sum < target) left++; // need a larger value\n else right--; // need a smaller value\n }\n return [-1, -1];\n}\n```\n\n\nFor `nums = [1, 3, 5, 7, 9, 11]` and `target = 12`, the algorithm checks `1 + 11 = 12` immediately and returns `[0, 5]`. For `target = 16`, the trace looks like this:\n\n\n| Step | left | right | sum | Action |\n| --- | --- | --- | --- | --- |\n| 1 | 0 | 5 | 12 | `12 < 16`, advance left |\n| 2 | 1 | 5 | 14 | `14 < 16`, advance left |\n| 3 | 2 | 5 | 16 | Found, return `[2, 5]` |\n\n\nThe brute-force version of this problem checks every pair in **O(n²)** time. Two pointers brings that down to **O(n)** time and **O(1)** extra space.\n\nCommon use cases for the two-pointer pattern:\n\n- Pair sum problems on sorted arrays (Two Sum II, 3Sum, 4Sum).\n- Removing duplicates from a sorted array in place.\n- Checking whether a string is a palindrome.\n- Merging two sorted arrays.\n\n### 2. Sliding Window\n\nSliding window applies to problems about a **contiguous subarray or substring**. Instead of recomputing a property (sum, count, frequency, max, etc.) for every possible subarray, you maintain a window that moves across the array, updating the property incrementally as elements enter and leave.\n\nThe visualization below shows a fixed-size window of width 3 sliding across the array:\n\n\n\n\nEach time the window slides one position to the right, exactly one element leaves the window and one new element enters. That **O(1)** update per shift is what makes the whole scan **O(n)**.\n\nA concrete example: find the **maximum sum of any contiguous subarray of size k**.\n\n\n```java\nint maxSumWindow(int[] nums, int k) {\n int sum = 0;\n for (int i = 0; i < k; i++) sum += nums[i]; // first window\n int maxSum = sum;\n for (int i = k; i < nums.length; i++) {\n sum += nums[i] - nums[i - k]; // slide by one\n maxSum = Math.max(maxSum, sum);\n }\n return maxSum;\n}\n```\n\n```python\ndef max_sum_window(nums, k):\n window = sum(nums[:k]) # first window\n max_sum = window\n for i in range(k, len(nums)):\n window += nums[i] - nums[i - k] # slide by one\n max_sum = max(max_sum, window)\n return max_sum\n```\n\n```cpp\nint maxSumWindow(std::vector& nums, int k) {\n int sum = 0;\n for (int i = 0; i < k; i++) sum += nums[i]; // first window\n int maxSum = sum;\n for (int i = k; i < (int)nums.size(); i++) {\n sum += nums[i] - nums[i - k]; // slide by one\n maxSum = std::max(maxSum, sum);\n }\n return maxSum;\n}\n```\n\n```csharp\npublic int MaxSumWindow(int[] nums, int k) {\n int sum = 0;\n for (int i = 0; i < k; i++) sum += nums[i]; // first window\n int maxSum = sum;\n for (int i = k; i < nums.Length; i++) {\n sum += nums[i] - nums[i - k]; // slide by one\n maxSum = Math.Max(maxSum, sum);\n }\n return maxSum;\n}\n```\n\n```go\nfunc maxSumWindow(nums []int, k int) int {\n sum := 0\n for i := 0; i < k; i++ {\n sum += nums[i] // first window\n }\n maxSum := sum\n for i := k; i < len(nums); i++ {\n sum += nums[i] - nums[i-k] // slide by one\n if sum > maxSum {\n maxSum = sum\n }\n }\n return maxSum\n}\n```\n\n```rust\npub fn max_sum_window(nums: &[i32], k: usize) -> i32 {\n let mut sum: i32 = nums[..k].iter().sum(); // first window\n let mut max_sum = sum;\n for i in k..nums.len() {\n sum += nums[i] - nums[i - k]; // slide by one\n max_sum = max_sum.max(sum);\n }\n max_sum\n}\n```\n\n```javascript\nfunction maxSumWindow(nums, k) {\n let sum = 0;\n for (let i = 0; i < k; i++) sum += nums[i]; // first window\n let maxSum = sum;\n for (let i = k; i < nums.length; i++) {\n sum += nums[i] - nums[i - k]; // slide by one\n maxSum = Math.max(maxSum, sum);\n }\n return maxSum;\n}\n```\n\n```typescript\nfunction maxSumWindow(nums: number[], k: number): number {\n let sum = 0;\n for (let i = 0; i < k; i++) sum += nums[i]; // first window\n let maxSum = sum;\n for (let i = k; i < nums.length; i++) {\n sum += nums[i] - nums[i - k]; // slide by one\n maxSum = Math.max(maxSum, sum);\n }\n return maxSum;\n}\n```\n\n\nRunning this on `nums = [1, 3, 5, 7, 9, 11]` with `k = 3`:\n\n\n| Window | Computation | Sum |\n| --- | --- | --- |\n| `[1, 3, 5]` | first window | 9 |\n| `[3, 5, 7]` | `9 + 7 − 1` | 15 |\n| `[5, 7, 9]` | `15 + 9 − 3` | 21 |\n| `[7, 9, 11]` | `21 + 11 − 5` | 27 |\n\n\nThe maximum is **27**. The naive approach (sum every length-`k` subarray from scratch) would cost **O(n × k)**; the sliding window does it in **O(n)**.\n\nSliding windows come in two flavors:\n\n- **Fixed-size windows** like the example above, where the window width is given.\n- **Variable-size windows**, where the window grows and shrinks based on a condition. *Longest substring without repeating characters* is the standard example: the right edge keeps expanding, and the left edge contracts whenever a duplicate appears inside the window.\n\nThis pattern fits problems like longest/shortest subarray with a property, maximum/minimum sum of subarrays, and counting substrings or subarrays that satisfy some constraint.\n\n### 3. Prefix Sum\n\nA **prefix sum array** stores the cumulative sum of all elements up to each index. With it, you can answer **range-sum queries** in **O(1)** instead of recomputing the sum on every query.\n\nFor an input array, `prefix[i]` is the sum of `nums[0] + nums[1] + ... + nums[i]`.\n\n**Input array:**\n\n\n\n\n**Prefix sum array:**\n\n\n\n\nThe second array is built from the first one position at a time:\n\n\n| i | Computation | prefix[i] |\n| --- | --- | --- |\n| 0 | `1` | 1 |\n| 1 | `1 + 3` | 4 |\n| 2 | `4 + 5` | 9 |\n| 3 | `9 + 7` | 16 |\n| 4 | `16 + 9` | 25 |\n| 5 | `25 + 11` | 36 |\n\n\nOnce the prefix array is built, the sum of any range `[L, R]` (inclusive) is just one subtraction:\n\n\n```javascript\nrangeSum(L, R) = prefix[R] − prefix[L − 1] // when L > 0\nrangeSum(0, R) = prefix[R] // when L == 0\n```\n\n\nFor example, the sum of `nums[2..4]` is `prefix[4] − prefix[1] = 25 − 4 = 21`, which matches `5 + 7 + 9`.\n\n\n```java\nclass RangeSum {\n int[] prefix;\n\n RangeSum(int[] nums) {\n prefix = new int[nums.length];\n prefix[0] = nums[0];\n for (int i = 1; i < nums.length; i++) {\n prefix[i] = prefix[i - 1] + nums[i];\n }\n }\n\n int query(int l, int r) {\n if (l == 0) return prefix[r];\n return prefix[r] - prefix[l - 1];\n }\n}\n```\n\n```python\nclass RangeSum:\n def __init__(self, nums):\n self.prefix = [0] * len(nums)\n self.prefix[0] = nums[0]\n for i in range(1, len(nums)):\n self.prefix[i] = self.prefix[i - 1] + nums[i]\n\n def query(self, l, r):\n if l == 0:\n return self.prefix[r]\n return self.prefix[r] - self.prefix[l - 1]\n```\n\n```cpp\nclass RangeSum {\n std::vector prefix;\npublic:\n RangeSum(const std::vector& nums) {\n prefix.resize(nums.size());\n prefix[0] = nums[0];\n for (size_t i = 1; i < nums.size(); i++) {\n prefix[i] = prefix[i - 1] + nums[i];\n }\n }\n\n int query(int l, int r) {\n if (l == 0) return prefix[r];\n return prefix[r] - prefix[l - 1];\n }\n};\n```\n\n```csharp\npublic class RangeSum {\n private int[] prefix;\n\n public RangeSum(int[] nums) {\n prefix = new int[nums.Length];\n prefix[0] = nums[0];\n for (int i = 1; i < nums.Length; i++) {\n prefix[i] = prefix[i - 1] + nums[i];\n }\n }\n\n public int Query(int l, int r) {\n if (l == 0) return prefix[r];\n return prefix[r] - prefix[l - 1];\n }\n}\n```\n\n```go\ntype RangeSum struct {\n prefix []int\n}\n\nfunc NewRangeSum(nums []int) *RangeSum {\n prefix := make([]int, len(nums))\n prefix[0] = nums[0]\n for i := 1; i < len(nums); i++ {\n prefix[i] = prefix[i-1] + nums[i]\n }\n return &RangeSum{prefix: prefix}\n}\n\nfunc (r *RangeSum) Query(l, right int) int {\n if l == 0 {\n return r.prefix[right]\n }\n return r.prefix[right] - r.prefix[l-1]\n}\n```\n\n```rust\npub struct RangeSum {\n prefix: Vec,\n}\n\nimpl RangeSum {\n pub fn new(nums: &[i32]) -> Self {\n let mut prefix = vec![0; nums.len()];\n prefix[0] = nums[0];\n for i in 1..nums.len() {\n prefix[i] = prefix[i - 1] + nums[i];\n }\n RangeSum { prefix }\n }\n\n pub fn query(&self, l: usize, r: usize) -> i32 {\n if l == 0 {\n self.prefix[r]\n } else {\n self.prefix[r] - self.prefix[l - 1]\n }\n }\n}\n```\n\n```javascript\nclass RangeSum {\n constructor(nums) {\n this.prefix = new Array(nums.length);\n this.prefix[0] = nums[0];\n for (let i = 1; i < nums.length; i++) {\n this.prefix[i] = this.prefix[i - 1] + nums[i];\n }\n }\n\n query(l, r) {\n if (l === 0) return this.prefix[r];\n return this.prefix[r] - this.prefix[l - 1];\n }\n}\n```\n\n```typescript\nclass RangeSum {\n private prefix: number[];\n\n constructor(nums: number[]) {\n this.prefix = new Array(nums.length);\n this.prefix[0] = nums[0];\n for (let i = 1; i < nums.length; i++) {\n this.prefix[i] = this.prefix[i - 1] + nums[i];\n }\n }\n\n query(l: number, r: number): number {\n if (l === 0) return this.prefix[r];\n return this.prefix[r] - this.prefix[l - 1];\n }\n}\n```\n\n\nConstruction costs **O(n)** time and **O(n)** extra space; each query then runs in **O(1)**. This is the right trade-off when there are many range queries on a static array.\n\nThe same idea extends to other associative operations: prefix XOR for range-XOR queries, prefix counts for \"how many even numbers in a range\", and 2D prefix sums for sub-rectangle sums in matrices.\n\n### 4. Dynamic Programming with Arrays\n\nMany dynamic programming problems use a 1D or 2D array (the **DP table**) to cache solutions to smaller subproblems. The DP table is just a flat array where each cell stores the answer to one well-defined subproblem.\n\nThe simplest example is **climbing stairs**: from step `0`, you can take 1-step or 2-step jumps; how many ways are there to reach step `n`?\n\nThe recurrence is:\n\n\n```javascript\nways[i] = ways[i − 1] + ways[i − 2]\nways[0] = 1\nways[1] = 1\n```\n\n\nThis is just the Fibonacci sequence in disguise. The array-based bottom-up implementation fills the DP table left to right:\n\n\n```java\nint climbStairs(int n) {\n if (n <= 1) return 1;\n int[] ways = new int[n + 1];\n ways[0] = 1;\n ways[1] = 1;\n for (int i = 2; i <= n; i++) {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n return ways[n];\n}\n```\n\n```python\ndef climb_stairs(n):\n if n <= 1:\n return 1\n ways = [0] * (n + 1)\n ways[0] = 1\n ways[1] = 1\n for i in range(2, n + 1):\n ways[i] = ways[i - 1] + ways[i - 2]\n return ways[n]\n```\n\n```cpp\nint climbStairs(int n) {\n if (n <= 1) return 1;\n std::vector ways(n + 1);\n ways[0] = 1;\n ways[1] = 1;\n for (int i = 2; i <= n; i++) {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n return ways[n];\n}\n```\n\n```csharp\npublic int ClimbStairs(int n) {\n if (n <= 1) return 1;\n int[] ways = new int[n + 1];\n ways[0] = 1;\n ways[1] = 1;\n for (int i = 2; i <= n; i++) {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n return ways[n];\n}\n```\n\n```go\nfunc climbStairs(n int) int {\n if n <= 1 {\n return 1\n }\n ways := make([]int, n+1)\n ways[0] = 1\n ways[1] = 1\n for i := 2; i <= n; i++ {\n ways[i] = ways[i-1] + ways[i-2]\n }\n return ways[n]\n}\n```\n\n```rust\npub fn climb_stairs(n: usize) -> i32 {\n if n <= 1 {\n return 1;\n }\n let mut ways = vec![0; n + 1];\n ways[0] = 1;\n ways[1] = 1;\n for i in 2..=n {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n ways[n]\n}\n```\n\n```javascript\nfunction climbStairs(n) {\n if (n <= 1) return 1;\n const ways = new Array(n + 1);\n ways[0] = 1;\n ways[1] = 1;\n for (let i = 2; i <= n; i++) {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n return ways[n];\n}\n```\n\n```typescript\nfunction climbStairs(n: number): number {\n if (n <= 1) return 1;\n const ways: number[] = new Array(n + 1);\n ways[0] = 1;\n ways[1] = 1;\n for (let i = 2; i <= n; i++) {\n ways[i] = ways[i - 1] + ways[i - 2];\n }\n return ways[n];\n}\n```\n\n\nFor `n = 5`, the table fills as `[1, 1, 2, 3, 5, 8]`, so there are 8 ways to reach step 5. Each cell is computed in **O(1)** by reading two earlier cells, so the whole algorithm is **O(n)** time and **O(n)** space (and can be reduced to **O(1)** space by keeping only the last two values).\n\nThe recipe behind every array-based DP problem is the same:\n\n1. Identify the subproblem each cell of the array represents.\n2. Write a recurrence that expresses the answer at cell `i` in terms of earlier cells.\n3. Define the base cases (the smallest subproblems).\n4. Fill the array in an order that guarantees every cell's dependencies are filled first.\n\nCommon interview problems that follow this pattern:\n\n- **House Robber** (1D): `dp[i] = max(dp[i − 1], dp[i − 2] + nums[i])`.\n- **Coin Change**: `dp[amount] = min over coins of (dp[amount − coin] + 1)`.\n- **Longest Increasing Subsequence**: `dp[i] = 1 + max(dp[j])` for `j < i` with `nums[j] < nums[i]`.\n- **0/1 Knapsack** (2D): `dp[i][w]` is the best value using the first `i` items with capacity `w`.\n\nMost of these patterns reuse the same array fundamentals covered earlier: indexed access, contiguous memory, and careful management of insertions and deletions. The four patterns above (two pointers, sliding window, prefix sum, dynamic programming) are what turn arrays from a storage container into a core tool for algorithmic problem solving.\n\n---\n\n# Quiz","pageType":"dsa"}

Introduction to Arrays

Get Premium