The most fundamental data structure in programming. Master arrays and you have the foundation for everything else in DSA.
An array is a collection of elements stored in contiguous (adjacent) memory locations. Because the elements sit right next to each other in memory, you can jump to any element instantly if you know its index. This is why array access is O(1) -- the computer calculates the exact memory address with simple arithmetic.
In low-level languages like C or Java, arrays have a fixed size -- you declare how many elements they hold at creation and that is it. You cannot grow or shrink them.
In Python and JavaScript, you work with dynamic arrays (Python's list, JavaScript's Array). These automatically resize when you add more elements than the current capacity allows. Under the hood, they allocate a new, larger block of memory and copy everything over. This resizing is why appending is O(1) amortized -- most appends are instant, but occasionally one triggers a costly resize.
Do not confuse "array" in C (fixed, contiguous, typed) with Python's list (dynamic, can hold mixed types). When interviewers say "array," they typically mean the logical concept -- an indexed, ordered collection -- regardless of language.
Here is how an array of integers looks in memory. Each cell is the same size, and the index determines the offset from the base address:
Because every element is the same size and stored contiguously, accessing arr[0] and arr[999999] takes the exact same amount of time. No scanning, no traversal -- just a direct memory lookup. This is the superpower of arrays compared to linked lists, where you would need to walk through every node.
Arrays are cache-friendly. Because elements are adjacent in memory, your CPU cache loads nearby elements automatically. Iterating through an array is one of the fastest operations a computer can do.
Understanding the time complexity of every operation is critical. This table is your cheat sheet for array operations:
| Operation | Fixed-Size Array | Dynamic Array | Why? |
|---|---|---|---|
| Access by index | O(1) | O(1) | Direct address calculation |
| Search (unsorted) | O(n) | O(n) | Must check each element |
| Search (sorted) | O(log n) | O(log n) | Binary search |
| Insert at end | N/A (fixed size) | O(1) amortized | Occasional resize costs O(n) |
| Insert at index | O(n) | O(n) | Must shift elements right |
| Delete from end | N/A | O(1) | No shifting needed |
| Delete at index | O(n) | O(n) | Must shift elements left |
To insert 99 at index 2 in [10, 20, 30, 40, 50]:
Step 1: Shift 30, 40, 50 one position right.
Step 2: Place 99 at index 2.
Result: [10, 20, 99, 30, 40, 50]. In the worst case (inserting at index 0), you shift all n elements.
Both Python and JavaScript create dynamic arrays with similar syntax:
Python
# Create an array (list in Python)
arr = [1, 2, 3, 4, 5]
# Create an empty array
empty = []
# Create array of n zeros
zeros = [0] * 10
# Create array with list comprehension
squares = [i**2 for i in range(5)]
# [0, 1, 4, 9, 16]JavaScript
// Create an array
const arr = [1, 2, 3, 4, 5];
// Create an empty array
const empty = [];
// Create array of n zeros
const zeros = new Array(10).fill(0);
// Create array with Array.from
const squares = Array.from(
{length: 5}, (_, i) => i ** 2
);
// [0, 1, 4, 9, 16]Access any element in O(1) using its index. Arrays are zero-indexed in both languages:
Python
arr = [10, 20, 30, 40, 50]
# Access by index
first = arr[0] # 10
third = arr[2] # 30
# Negative indexing (Python-only!)
last = arr[-1] # 50
second_last = arr[-2] # 40
# Length
size = len(arr) # 5JavaScript
const arr = [10, 20, 30, 40, 50];
// Access by index
const first = arr[0]; // 10
const third = arr[2]; // 30
// Last element (no negative indexing)
const last = arr[arr.length - 1]; // 50
// Or use .at() in modern JS
const alsoLast = arr.at(-1); // 50
// Length
const size = arr.length; // 5Traversal means visiting every element. There are multiple ways to loop through an array:
Python
arr = [10, 20, 30, 40]
# Method 1: Simple for loop
for val in arr:
print(val)
# Method 2: With index using enumerate
for i, val in enumerate(arr):
print(f"Index {i}: {val}")
# Method 3: Index-based loop
for i in range(len(arr)):
print(arr[i])
# Method 4: While loop
i = 0
while i < len(arr):
print(arr[i])
i += 1JavaScript
const arr = [10, 20, 30, 40];
// Method 1: for...of loop
for (const val of arr) {
console.log(val);
}
// Method 2: forEach with index
arr.forEach((val, i) => {
console.log(`Index ${i}: ${val}`);
});
// Method 3: Classic for loop
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
// Method 4: While loop
let i = 0;
while (i < arr.length) {
console.log(arr[i]);
i++;
}In Python, prefer for val in arr for simple iteration and for i, val in enumerate(arr) when you need the index. The range(len(arr)) pattern is considered less Pythonic but is sometimes necessary for two-pointer patterns.
Adding elements to a dynamic array:
Python
arr = [1, 2, 3]
# Append to end -- O(1) amortized
arr.append(4)
# [1, 2, 3, 4]
# Insert at specific index -- O(n)
arr.insert(1, 99)
# [1, 99, 2, 3, 4]
# Extend with another list -- O(k)
arr.extend([5, 6])
# [1, 99, 2, 3, 4, 5, 6]
# Concatenation (creates new list)
new_arr = arr + [7, 8]JavaScript
const arr = [1, 2, 3];
// Push to end -- O(1) amortized
arr.push(4);
// [1, 2, 3, 4]
// Insert at specific index -- O(n)
arr.splice(1, 0, 99);
// [1, 99, 2, 3, 4]
// Push multiple elements
arr.push(5, 6);
// [1, 99, 2, 3, 4, 5, 6]
// Unshift to front -- O(n)
arr.unshift(0);
// [0, 1, 99, 2, 3, 4, 5, 6]Python
arr = [10, 20, 30, 40, 50]
# Pop last element -- O(1)
last = arr.pop()
# last = 50, arr = [10, 20, 30, 40]
# Pop at specific index -- O(n)
second = arr.pop(1)
# second = 20, arr = [10, 30, 40]
# Remove by value -- O(n)
arr.remove(30)
# arr = [10, 40]
# Delete by index
del arr[0]
# arr = [40]
# Clear entire list
arr.clear()
# arr = []JavaScript
const arr = [10, 20, 30, 40, 50];
// Pop last element -- O(1)
const last = arr.pop();
// last = 50, arr = [10, 20, 30, 40]
// Remove at index using splice -- O(n)
const removed = arr.splice(1, 1);
// removed = [20], arr = [10, 30, 40]
// Shift removes first element -- O(n)
const first = arr.shift();
// first = 10, arr = [30, 40]
// Filter to remove by value -- O(n)
let filtered = arr.filter(x => x !== 30);
// filtered = [40]
// Clear entire array
arr.length = 0;
// arr = []Slicing extracts a sub-array without modifying the original. Both languages use start-inclusive, end-exclusive ranges:
Python
arr = [10, 20, 30, 40, 50]
# Basic slice: arr[start:end]
sub = arr[1:4]
# [20, 30, 40]
# From beginning
first_three = arr[:3]
# [10, 20, 30]
# To end
last_two = arr[3:]
# [40, 50]
# With step
every_other = arr[::2]
# [10, 30, 50]
# Reverse an array
reversed_arr = arr[::-1]
# [50, 40, 30, 20, 10]
# Shallow copy
copy = arr[:]JavaScript
const arr = [10, 20, 30, 40, 50];
// Basic slice: arr.slice(start, end)
const sub = arr.slice(1, 4);
// [20, 30, 40]
// From beginning
const firstThree = arr.slice(0, 3);
// [10, 20, 30]
// To end
const lastTwo = arr.slice(3);
// [40, 50]
// No step parameter -- use filter
const everyOther = arr.filter(
(_, i) => i % 2 === 0
);
// [10, 30, 50]
// Reverse (mutates original!)
const rev = [...arr].reverse();
// [50, 40, 30, 20, 10]
// Shallow copy
const copy = [...arr];In JavaScript, .reverse() mutates the original array. Always spread into a new array first with [...arr].reverse() if you need to preserve the original. Python's arr[::-1] creates a new list and does not mutate.
Linear search checks each element one by one. It is O(n) in the worst case:
Python
def linear_search(arr, target):
"""Return index of target, or -1 if not found."""
for i, val in enumerate(arr):
if val == target:
return i
return -1
# Usage
arr = [5, 3, 8, 1, 9]
idx = linear_search(arr, 8) # 2
idx = linear_search(arr, 7) # -1
# Built-in alternatives:
8 in arr # True (O(n))
arr.index(8) # 2 (raises ValueError if not found)JavaScript
function linearSearch(arr, target) {
// Return index of target, or -1
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
// Usage
const arr = [5, 3, 8, 1, 9];
linearSearch(arr, 8); // 2
linearSearch(arr, 7); // -1
// Built-in alternatives:
arr.includes(8); // true (O(n))
arr.indexOf(8); // 2 (-1 if not found)Python
arr = [5, 2, 8, 1, 9, 3]
# Sort in-place -- O(n log n)
arr.sort()
# arr = [1, 2, 3, 5, 8, 9]
# Sort descending
arr.sort(reverse=True)
# arr = [9, 8, 5, 3, 2, 1]
# Create new sorted list (original unchanged)
original = [5, 2, 8]
new_sorted = sorted(original)
# original = [5, 2, 8]
# new_sorted = [2, 5, 8]
# Sort with custom key
words = ["banana", "fig", "cherry"]
words.sort(key=len)
# ["fig", "banana", "cherry"]JavaScript
const arr = [5, 2, 8, 1, 9, 3];
// Sort in-place -- O(n log n)
// WARNING: default sort is lexicographic!
arr.sort((a, b) => a - b);
// arr = [1, 2, 3, 5, 8, 9]
// Sort descending
arr.sort((a, b) => b - a);
// arr = [9, 8, 5, 3, 2, 1]
// Create new sorted array
const original = [5, 2, 8];
const newSorted = [...original].sort(
(a, b) => a - b
);
// original = [5, 2, 8] (unchanged)
// Sort with custom comparator
const words = ["banana", "fig", "cherry"];
words.sort((a, b) => a.length - b.length);
// ["fig", "banana", "cherry"]JavaScript's default .sort() converts elements to strings and sorts lexicographically. This means [10, 9, 80].sort() gives [10, 80, 9] -- not [9, 10, 80]. Always pass a comparator when sorting numbers: arr.sort((a, b) => a - b).
These three techniques show up in the majority of array interview problems. Learn them deeply and you will recognize them instantly.
The two-pointer technique uses two indices that move through the array, typically from opposite ends or at different speeds. It reduces brute-force O(n^2) solutions to O(n) by eliminating redundant comparisons.
Example: Two Sum on a Sorted Array
Given a sorted array and a target, find two numbers that add up to the target. Return their indices.
arr = [1, 3, 5, 7, 11, 15], target = 12
Left pointer at index 0 (value 1), right pointer at index 5 (value 15).
1 + 15 = 16 > 12 --> Move right pointer left.
1 + 11 = 12 = target --> Found it! Return [0, 4].
Key insight: if the sum is too big, decreasing the right side makes it smaller. If the sum is too small, increasing the left side makes it bigger.
Python
def two_sum_sorted(arr, target):
"""
Find two numbers in sorted array
that add up to target.
Returns their indices.
"""
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # Need bigger sum
else:
right -= 1 # Need smaller sum
return [] # No pair found
# Usage
arr = [1, 3, 5, 7, 11, 15]
print(two_sum_sorted(arr, 12))
# [0, 4] (arr[0] + arr[4] = 1 + 11 = 12)JavaScript
function twoSumSorted(arr, target) {
/**
* Find two numbers in sorted array
* that add up to target.
* Returns their indices.
*/
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++; // Need bigger sum
} else {
right--; // Need smaller sum
}
}
return []; // No pair found
}
// Usage
const arr = [1, 3, 5, 7, 11, 15];
console.log(twoSumSorted(arr, 12));
// [0, 4] (arr[0] + arr[4] = 1 + 11 = 12)The sliding window technique maintains a "window" (a contiguous sub-array) that slides across the array. Instead of recomputing the entire window from scratch at every position, you add the new element entering the window and remove the element leaving it. This turns O(n*k) brute-force into O(n).
Example: Maximum Sum Subarray of Size k
Given an array and a window size k, find the maximum sum of any contiguous subarray of length k.
arr = [2, 1, 5, 1, 3, 2], k = 3
Window [2, 1, 5] = 8
Slide: remove 2, add 1 --> [1, 5, 1] = 7
Slide: remove 1, add 3 --> [5, 1, 3] = 9
Slide: remove 5, add 2 --> [1, 3, 2] = 6
Maximum sum = 9
Python
def max_sum_subarray(arr, k):
"""
Find maximum sum of any contiguous
subarray of size k.
"""
if len(arr) < k:
return 0
# Calculate sum of first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window
for i in range(k, len(arr)):
# Add new element, remove old
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# Usage
arr = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray(arr, 3))
# 9 (subarray [5, 1, 3])JavaScript
function maxSumSubarray(arr, k) {
/**
* Find maximum sum of any contiguous
* subarray of size k.
*/
if (arr.length < k) return 0;
// 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++) {
// Add new element, remove old
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Usage
const arr = [2, 1, 5, 1, 3, 2];
console.log(maxSumSubarray(arr, 3));
// 9 (subarray [5, 1, 3])A prefix sum array stores the cumulative sum up to each index. Once built (O(n) time), you can answer any "sum of elements from index i to j" query in O(1) time. Without prefix sums, each range sum query would take O(n).
arr = [2, 4, 6, 8, 10]
prefix = [0, 2, 6, 12, 20, 30]
Sum from index 1 to 3 = prefix[4] - prefix[1] = 20 - 2 = 18
Verify: arr[1] + arr[2] + arr[3] = 4 + 6 + 8 = 18
Python
def build_prefix_sum(arr):
"""Build prefix sum array."""
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix, i, j):
"""Sum of arr[i..j] in O(1)."""
return prefix[j + 1] - prefix[i]
# Usage
arr = [2, 4, 6, 8, 10]
prefix = build_prefix_sum(arr)
# prefix = [0, 2, 6, 12, 20, 30]
print(range_sum(prefix, 1, 3))
# 18 (4 + 6 + 8)
print(range_sum(prefix, 0, 4))
# 30 (2 + 4 + 6 + 8 + 10)
print(range_sum(prefix, 2, 2))
# 6 (just arr[2])JavaScript
function buildPrefixSum(arr) {
/** Build prefix sum array. */
const prefix = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}
function rangeSum(prefix, i, j) {
/** Sum of arr[i..j] in O(1). */
return prefix[j + 1] - prefix[i];
}
// Usage
const arr = [2, 4, 6, 8, 10];
const prefix = buildPrefixSum(arr);
// prefix = [0, 2, 6, 12, 20, 30]
console.log(rangeSum(prefix, 1, 3));
// 18 (4 + 6 + 8)
console.log(rangeSum(prefix, 0, 4));
// 30 (2 + 4 + 6 + 8 + 10)
console.log(rangeSum(prefix, 2, 2));
// 6 (just arr[2])Prefix sums appear in disguise in many problems. Anytime you see "sum of subarray" or "range query," think prefix sums. The technique extends to 2D arrays (prefix sum matrices) for submatrix sum queries.
A string is essentially a sequence (array) of characters. You can index into a string, iterate over it, and slice it just like an array. However, strings have one critical difference in both Python and JavaScript: they are immutable.
In both Python and JavaScript, strings cannot be modified in-place. Every "modification" creates a new string. This means string concatenation in a loop is O(n^2) because each concatenation creates a new string and copies all previous characters.
Python
s = "hello"
# Strings are immutable
# s[0] = "H" # TypeError!
# Index access (just like arrays)
first = s[0] # "h"
last = s[-1] # "o"
# Iterate like an array
for char in s:
print(char)
# To "modify," convert to list first
chars = list(s) # ['h','e','l','l','o']
chars[0] = "H"
s = "".join(chars) # "Hello"
# Efficient concatenation: use join
parts = ["a", "b", "c"]
result = "".join(parts) # "abc" -- O(n)JavaScript
const s = "hello";
// Strings are immutable
// s[0] = "H"; // Silently fails!
// Index access (just like arrays)
const first = s[0]; // "h"
const last = s[s.length - 1]; // "o"
// Iterate like an array
for (const char of s) {
console.log(char);
}
// To "modify," convert to array first
const chars = s.split("");
chars[0] = "H";
const newS = chars.join(""); // "Hello"
// Efficient concatenation: use join
const parts = ["a", "b", "c"];
const result = parts.join(""); // "abc"Python
def reverse_string(s):
"""Reverse a string."""
return s[::-1]
# Or manually with two pointers:
def reverse_string_manual(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = (
chars[right], chars[left]
)
left += 1
right -= 1
return "".join(chars)
print(reverse_string("hello"))
# "olleh"JavaScript
function reverseString(s) {
/** Reverse a string. */
return s.split("").reverse().join("");
}
// Or manually with two pointers:
function reverseStringManual(s) {
const chars = s.split("");
let left = 0;
let right = chars.length - 1;
while (left < right) {
[chars[left], chars[right]] =
[chars[right], chars[left]];
left++;
right--;
}
return chars.join("");
}
console.log(reverseString("hello"));
// "olleh"A palindrome reads the same forwards and backwards (e.g., "racecar", "madam").
Python
def is_palindrome(s):
"""Check if string is a palindrome."""
# Clean: lowercase, letters/digits only
s = "".join(
c.lower() for c in s if c.isalnum()
)
return s == s[::-1]
# Two-pointer approach (O(1) extra space):
def is_palindrome_tp(s):
s = "".join(
c.lower() for c in s if c.isalnum()
)
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False
print(is_palindrome("A man, a plan, a canal: Panama"))
# TrueJavaScript
function isPalindrome(s) {
/** Check if string is a palindrome. */
// Clean: lowercase, letters/digits only
s = s.toLowerCase().replace(
/[^a-z0-9]/g, ""
);
return s === s.split("").reverse().join("");
}
// Two-pointer approach:
function isPalindromeTP(s) {
s = s.toLowerCase().replace(
/[^a-z0-9]/g, ""
);
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false;
}
left++;
right--;
}
return true;
}
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false
console.log(isPalindrome(
"A man, a plan, a canal: Panama"
)); // trueTwo strings are anagrams if they contain exactly the same characters in any order (e.g., "listen" and "silent").
Python
def is_anagram(s1, s2):
"""Check if two strings are anagrams."""
# Method 1: Sort and compare -- O(n log n)
return sorted(s1.lower()) == sorted(s2.lower())
def is_anagram_optimal(s1, s2):
"""O(n) using character frequency."""
if len(s1) != len(s2):
return False
# Count character frequencies
count = {}
for c in s1.lower():
count[c] = count.get(c, 0) + 1
for c in s2.lower():
count[c] = count.get(c, 0) - 1
if count[c] < 0:
return False
return True
print(is_anagram("listen", "silent"))
# True
print(is_anagram("hello", "world"))
# FalseJavaScript
function isAnagram(s1, s2) {
/** Check if two strings are anagrams. */
// Method 1: Sort and compare -- O(n log n)
const sort = s =>
s.toLowerCase().split("").sort().join("");
return sort(s1) === sort(s2);
}
function isAnagramOptimal(s1, s2) {
/** O(n) using character frequency. */
if (s1.length !== s2.length) return false;
const count = {};
for (const c of s1.toLowerCase()) {
count[c] = (count[c] || 0) + 1;
}
for (const c of s2.toLowerCase()) {
if (!count[c]) return false;
count[c]--;
}
return true;
}
console.log(isAnagram("listen", "silent"));
// true
console.log(isAnagram("hello", "world"));
// falseThe sorting approach (O(n log n)) is simpler to write and fewer lines. The frequency-count approach (O(n)) is optimal. In an interview, mention both and implement the optimal one. The interviewer wants to see that you know the tradeoff.
These are the essential array/string problems ordered by difficulty. Solve them in order for the best learning experience.
| Problem | Difficulty | Key Technique | Approach Hint |
|---|---|---|---|
| Two Sum | Easy | Hash Map | Store complement in hash map as you iterate |
| Best Time to Buy and Sell Stock | Easy | Tracking Min | Track minimum price seen so far, compute max profit at each step |
| Contains Duplicate | Easy | Set | Add to set; if element already in set, return true |
| Maximum Subarray | Medium | Kadane's Algorithm | At each index, decide: extend current subarray or start fresh |
| Product of Array Except Self | Medium | Prefix / Suffix | Build prefix product from left, then multiply with suffix from right |
| 3Sum | Medium | Sort + Two Pointers | Sort array, fix one number, use two pointers on remaining |
| Container With Most Water | Medium | Two Pointers | Start from edges; move the shorter pointer inward |
| Merge Intervals | Medium | Sorting | Sort by start time, merge overlapping intervals greedily |
| Trapping Rain Water | Hard | Two Pointers / Stack | Water at each index = min(max_left, max_right) - height[i] |
Problem: Given an array of integers nums and a target, return the indices of the two numbers that add up to the target. You may assume each input has exactly one solution.
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9
Approach: For each number, its complement is target - number. We store each number we have seen in a hash map. If the complement of the current number exists in the map, we found our pair.
Python
def two_sum(nums, target):
"""
LeetCode 1 - Two Sum
Return indices of two numbers that
add up to target.
Time: O(n) | Space: O(n)
"""
# Map: value -> index
seen = {}
for i, num in enumerate(nums):
complement = target - num
# Have we seen the complement?
if complement in seen:
return [seen[complement], i]
# Store current number and index
seen[num] = i
return [] # No solution
# Test cases
print(two_sum([2, 7, 11, 15], 9))
# [0, 1]
print(two_sum([3, 2, 4], 6))
# [1, 2]
print(two_sum([3, 3], 6))
# [0, 1]JavaScript
function twoSum(nums, target) {
/**
* LeetCode 1 - Two Sum
* Return indices of two numbers that
* add up to target.
* Time: O(n) | Space: O(n)
*/
// Map: value -> index
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
// Have we seen the complement?
if (seen.has(complement)) {
return [seen.get(complement), i];
}
// Store current number and index
seen.set(nums[i], i);
}
return []; // No solution
}
// Test cases
console.log(twoSum([2, 7, 11, 15], 9));
// [0, 1]
console.log(twoSum([3, 2, 4], 6));
// [1, 2]
console.log(twoSum([3, 3], 6));
// [0, 1]At index i, we ask: "Have I already seen a number that, combined with nums[i], equals the target?" The hash map lookup is O(1), so the total time is O(n). We only need one pass through the array.
Problem: Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 (subarray [4, -1, 2, 1] has the largest sum)
Approach (Kadane's Algorithm): At each index, you make a simple decision: either extend the current subarray by adding the current element, or start a new subarray from the current element. You pick whichever gives a larger value. Track the global maximum as you go.
Python
def max_subarray(nums):
"""
LeetCode 53 - Maximum Subarray
Kadane's Algorithm.
Time: O(n) | Space: O(1)
"""
current_sum = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
# Extend or start fresh?
current_sum = max(
nums[i],
current_sum + nums[i]
)
# Update global max
max_sum = max(max_sum, current_sum)
return max_sum
# Test cases
print(max_subarray(
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([1]))
# 1
print(max_subarray([-1, -2, -3]))
# -1 (least negative = largest)
print(max_subarray([5, 4, -1, 7, 8]))
# 23 (entire array)JavaScript
function maxSubarray(nums) {
/**
* LeetCode 53 - Maximum Subarray
* Kadane's Algorithm.
* Time: O(n) | Space: O(1)
*/
let currentSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
// Extend or start fresh?
currentSum = Math.max(
nums[i],
currentSum + nums[i]
);
// Update global max
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// Test cases
console.log(maxSubarray(
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
));
// 6 (subarray [4, -1, 2, 1])
console.log(maxSubarray([1]));
// 1
console.log(maxSubarray([-1, -2, -3]));
// -1 (least negative = largest)
console.log(maxSubarray([5, 4, -1, 7, 8]));
// 23 (entire array)nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
i=0: current=-2, max=-2
i=1: max(1, -2+1) = max(1, -1) = 1, max=1
i=2: max(-3, 1-3) = max(-3, -2) = -2, max=1
i=3: max(4, -2+4) = max(4, 2) = 4, max=4
i=4: max(-1, 4-1) = max(-1, 3) = 3, max=4
i=5: max(2, 3+2) = max(2, 5) = 5, max=5
i=6: max(1, 5+1) = max(1, 6) = 6, max=6
i=7: max(-5, 6-5) = max(-5, 1) = 1, max=6
i=8: max(4, 1+4) = max(4, 5) = 5, max=6
Answer: 6 (subarray [4, -1, 2, 1] from indices 3 to 6)
Test your understanding of arrays and strings. Click an answer to check it.
base_address + (index * element_size). This is a single arithmetic operation regardless of array size, making it constant time.
max(nums[i], current_sum + nums[i]). If the running sum has gone negative, adding to it would only drag down the current element, so it is better to start a fresh subarray from the current element.
s += char) considered O(n^2) in Python?s += char creates an entirely new string and copies all existing characters plus the new one. After n iterations, you have copied 1 + 2 + 3 + ... + n = n(n+1)/2 characters total, which is O(n^2). The fix: collect characters in a list and use "".join(list) at the end for O(n) total.