</>
Loading
Loading
The Foundation of Data Structures
8 of 45 problems completed
Arrays are the most fundamental data structure in computer science. They provide a way to store multiple elements of the same type in contiguous memory locations, enabling efficient access and manipulation of data.
An array is a collection of elements stored at contiguous memory locations. Each element can be accessed directly using its index, making arrays extremely efficient for random access operations.
In most languages, arrays have O(1) access time because the memory address of any element can be calculated directly: address = base_address + (index × element_size)
// Array declaration and initialization
const arr = [1, 2, 3, 4, 5];
// Access element - O(1)
const element = arr[2]; // 3
// Update element - O(1)
arr[2] = 10;
// Get length - O(1)
const length = arr.length; // 5Understanding the time complexity of array operations is crucial for writing efficient algorithms.
// Insert at end - O(1) amortized
arr.push(6);
// Insert at beginning - O(n)
arr.unshift(0);
// Remove from end - O(1)
arr.pop();
// Remove from beginning - O(n)
arr.shift();
// Insert/Remove at index - O(n)
arr.splice(2, 0, 'new'); // insert
arr.splice(2, 1); // removeOperations at the beginning of an array require shifting all other elements, resulting in O(n) time complexity. Consider using a deque if you need frequent insertions/deletions at both ends.
The two-pointer technique uses two indices to traverse an array, often from opposite ends or at different speeds. This approach can reduce time complexity from O(n²) to O(n) for many problems.
// Two Sum II - Input Array Is Sorted
function twoSum(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [-1, -1];
}The two-pointer technique works best on sorted arrays. If the array is unsorted, consider sorting it first (O(n log n)) or using a hash map instead.
Start pointers at both ends and move toward the center
Both pointers start at the beginning, one moves faster
The sliding window technique maintains a "window" of elements and slides it across the array. It's particularly useful for problems involving subarrays or substrings.
// Maximum Sum Subarray of Size K
function maxSumSubarray(arr, k) {
if (arr.length < k) return null;
// Calculate sum of first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
// Slide the window
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Fixed-size windows are simpler, but variable-size windows (expand/shrink based on conditions) are more versatile and appear in harder problems.
Access: O(1), Search: O(n), Insert/Delete: O(n)
Arrays use O(n) space where n is the number of elements
Many array problems can be solved with O(1) extra space by modifying the array directly
Use two indices to traverse the array efficiently
let left = 0, right = arr.length - 1;
while (left < right) {
// Process and move pointers
}Maintain a window of elements and slide it across
let left = 0;
for (let right = 0; right < arr.length; right++) {
// Expand window
while (/* condition to shrink */) {
// Shrink window
left++;
}
// Update result
}Precompute cumulative sums for range queries
const prefix = [0];
for (const num of arr) {
prefix.push(prefix[prefix.length - 1] + num);
}
// Sum of arr[i..j] = prefix[j+1] - prefix[i]After mastering arrays, move on to Strings to learn similar techniques applied to character sequences, then Hash Tables for O(1) lookup patterns.