Arrays
Arrays are fundamental data structures that form the building blocks of most algorithms. This module covers the essential concepts, operations, and common patterns for working with arrays.
Module Contents
Learning Resources
Introduction to Arrays
An array is a collection of elements stored at contiguous memory locations. It is the simplest data structure where each element can be accessed directly using its index.
Key Characteristics
- Fixed size (in most languages)
- Homogeneous elements (same data type)
- Random access (O(1) time complexity)
- Contiguous memory allocation
Common Operations
| Operation | Time Complexity | Description |
|---|---|---|
| Access | O(1) | Accessing an element at a given index |
| Search | O(n) | Finding an element in an unsorted array |
| Insert | O(n) | Inserting an element (may require shifting elements) |
| Delete | O(n) | Deleting an element (may require shifting elements) |
Array Implementation
Java Implementation
// Declaring and initializing arrays in Java
// Fixed-size array
int[] fixedArray = new int[5]; // Creates an array of size 5 with default values (0)
// Initialize with values
int[] initializedArray = {1, 2, 3, 4, 5}; // Creates and initializes an array
// Accessing elements
int thirdElement = initializedArray[2]; // Arrays are 0-indexed, so this gets the 3rd element (value 3)
// Modifying elements
initializedArray[1] = 10; // Changes the second element to 10
// Array length
int length = initializedArray.length; // Gets the length of the array
// Dynamic arrays using ArrayList
import java.util.ArrayList;
ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(1); // Adds element to the end
dynamicArray.add(2);
dynamicArray.add(3);
dynamicArray.get(1); // Gets element at index 1 (value 2)
dynamicArray.set(1, 10); // Sets element at index 1 to 10
dynamicArray.remove(0); // Removes element at index 0
dynamicArray.size(); // Gets the size of the ArrayListPython Implementation
# Declaring and initializing arrays (lists) in Python
# Python lists are dynamic by default
my_list = [1, 2, 3, 4, 5] # Creates and initializes a list
# Accessing elements
third_element = my_list[2] # Lists are 0-indexed, so this gets the 3rd element (value 3)
# Modifying elements
my_list[1] = 10 # Changes the second element to 10
# List length
length = len(my_list) # Gets the length of the list
# Common list operations
my_list.append(6) # Adds element to the end
my_list.insert(1, 7) # Inserts 7 at index 1
my_list.pop() # Removes and returns the last element
my_list.pop(0) # Removes and returns element at index 0
my_list.remove(3) # Removes the first occurrence of value 3
# List slicing
sub_list = my_list[1:4] # Gets elements from index 1 to 3
reversed_list = my_list[::-1] # Reverses the list
# List comprehension
squares = [x**2 for x in range(10)] # Creates a list of squares from 0 to 9Common Array Patterns
1. Two Pointers Technique
Using two pointers to solve array problems efficiently, often reducing the time complexity from O(n²) to O(n).
// Java implementation of Two Sum using two pointers
// (array must be sorted for this approach)
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] {left + 1, right + 1}; // 1-indexed result
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[] {-1, -1}; // No solution found
}2. Sliding Window
Using a window that slides through an array to efficiently process subarrays.
# Python implementation of Maximum Sum Subarray of size K
def max_sum_subarray(arr, k):
n = len(arr)
if n < k:
return -1
# Compute sum of first window of size k
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window from left to right
for i in range(n - k):
window_sum = window_sum - arr[i] + arr[i + k]
max_sum = max(max_sum, window_sum)
return max_sum3. Prefix Sum
Precomputing cumulative sums to efficiently calculate the sum of any subarray in O(1) time.
// Java implementation of Range Sum Query using Prefix Sum
class NumArray {
private int[] prefixSum;
public NumArray(int[] nums) {
prefixSum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
}
// Returns the sum of elements in the range [left, right] inclusive
public int sumRange(int left, int right) {
return prefixSum[right + 1] - prefixSum[left];
}
}Practice Problems
Apply your knowledge of arrays by solving these carefully selected problems:
1. Two Sum
Given an array of integers and a target sum, return indices of the two numbers that add up to the target.
2. Maximum Subarray
Find the contiguous subarray with the largest sum.
3. Container With Most Water
Find two lines that together with the x-axis form a container that holds the most water.
4. Product of Array Except Self
Given an array, return an array where each element is the product of all elements except itself.