3 Arrays
Arrays
The fundamental building blocks of linear data storage. Mastering traversal and manipulation.
4 // Arrays: Where It All Begins
Arrays were the first data structure I learned, and honestly, I underestimated them. “It’s just a list,” I thought. But as I dug deeper, I realized that simple arrays are the building blocks for almost everything else.
My biggest realization: Most array problems aren’t about the array itself, but about how you traverse it.
4.1 Table of Contents
4.2 Introduction to Arrays
4.2.1 Properties of Arrays
- Fixed Size: Traditional arrays have a fixed size determined at creation
- Contiguous Memory: Elements are stored in adjacent memory locations
- Zero-based Indexing: First element is at index 0
- Homogeneous Elements: All elements are of the same type
4.2.2 Time Complexity
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insertion | O(n) |
| Deletion | O(n) |
4.3 Basic Operations
4.3.1 Initialization
# Python
arr = [1, 2, 3, 4, 5] # List (dynamic array)
arr = [0] * 10 # Initialize with zeros
arr = [i for i in range(10)] # List comprehension4.3.2 Common Operations
# Access
first = arr[0] # O(1)
last = arr[-1] # O(1) in Python
# Search
try:
index = arr.index(3) # O(n)
except ValueError:
print("Not found")
# Insertion (for dynamic arrays like Python lists)
arr.append(6) # O(1) amortized
arr.insert(0, 0) # O(n)
# Deletion
popped = arr.pop() # O(1) from end
removed = arr.pop(0) # O(n) from beginning
arr.remove(3) # O(n) by value4.4 Common Patterns
4.4.1 Two Pointers
Two pointers is a technique where we maintain two references to positions in the array and move them based on certain conditions.
4.4.2 Sliding Window
The sliding window technique is used to perform a required operation on a specific window size of a given array or linked list.
4.4.3 Prefix Sum
Prefix sum is a technique that creates an auxiliary array where each element at index i represents the sum of all elements from the start up to index i in the original array.
When to use: - When you need to calculate the sum of subarrays quickly - When the array is immutable and you need to answer many range sum queries - When the problem can be transformed into a prefix sum problem
Example: Calculate the sum of elements between indices i and j (inclusive).
class PrefixSum:
def __init__(self, nums):
self.prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def range_sum(self, i, j):
return self.prefix[j + 1] - self.prefix[i]4.5 Practice Problems
4.5.1 Easy
- Remove Duplicates from Sorted Array
- Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
- Best Time to Buy and Sell Stock
- You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction.
4.5.2 Medium
- Container With Most Water
- Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
- 3Sum
- Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
4.5.3 Hard
- Trapping Rain Water
- Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
4.6 Solutions
4.6.1 1. Remove Duplicates from Sorted Array
def remove_duplicates(nums):
if not nums:
return 0
# Two pointers approach
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 14.6.2 2. Best Time to Buy and Sell Stock
def max_profit(prices):
if not prices:
return 0
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit4.6.3 3. Container With Most Water
def max_area(height):
max_area = 0
left, right = 0, len(height) - 1
while left < right:
# Calculate the area between the two lines
width = right - left
h = min(height[left], height[right])
max_area = max(max_area, width * h)
# Move the pointer pointing to the shorter line
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area4.6.4 4. 3Sum
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result4.6.5 5. Trapping Rain Water
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water4.7 Next Steps
In the next sections, we’ll explore more advanced array techniques and solve more complex problems. Practice these patterns to build your problem-solving skills.