Skip to content

Arrays and Strings

Two pointers

Two pointers involve having two integer variables that traverse an iterable.

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. left++
            2. right--
            3. Both left++ and right--

Example 1: Check if palindrome

Problem Description - Easy

Check if a string s is a palindrome (reads the same forward as backward)

1
2
3
4
5
6
7
8
9
def check_if_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
  • Time complexity: O(n) - maximum n while loop iterations, each cost O(1). Two pointers start at a distance of n, and move closer by one step each iteration.
  • Space complexity: O(1) - always use two integer variables.

Example 2: Check for target

Problem Description - Easy

Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target, false otherwise. This problem is similar to Two Sum. (In Two Sum, the input is not sorted).

For example, given nums = [1, 2, 4, 6, 8, 9, 14, 15] and target = 13, return true because 4 + 9 = 13.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def check_for_target(nums, target):
    left = 0
    right = len(nums) - 1
    while left < right:
        curr = nums[left] + nums[right]
        if curr == target:
            return True
        if curr > target:
            right -= 1
        else:
            left += 1
    return False

Another way to use two pointers

function fn(arr1, arr2):
    i = j = 0
    while i < arr1.length AND j < arr2.length:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. i++
            2. j++
            3. Both i++ and j++

    // Step 4: make sure both iterables are exhausted
    // Note that only one of these loops would run
    while i < arr1.length:
        Do some logic here depending on the problem
        i++

    while j < arr2.length:
        Do some logic here depending on the problem
        j++

Example 3 - Combine sorted array

Problem Description - Easy

Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def combine(arr1, arr2):
    # ans is the answer
    ans = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            ans.append(arr1[i])
            i += 1
        else:
            ans.append(arr2[j])
            j += 1
    # After the above loop, one of the two array is exhausted, running the below loop
    # to exhaust all the arrays

    while i < len(arr1):
        ans.append(arr1[i])
        i += 1

    while j < len(arr2):
        ans.append(arr2[j])
        j += 1

    return ans

392. Is subsequence

Problem Description - Easy

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a sequence of characters that can be obtained by deleting some (or none) of the characters from the original string, while maintaining the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not.

1
2
3
4
5
6
7
def is_sub_sequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

344. Reverse String

Problem Description - Easy

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

1
2
3
4
5
6
7
8
def reverse_string(s):
    left = 0
    right = len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left, right = left + 1, right - 1
    # Time: O(n) to swap n/2 times
    # Space: O(1), use only 2 integers

977. Squares of a Sorted array

Problem Description - Easy

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def sorted_squares(nums):
    n = len(nums)
    left = 0
    right = n - 1
    result = [0] * n
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            result[i] = nums[right] ** 2
            right -= 1
        else:
            result[i] = nums[left] ** 2
            left += 1
    return result
    # Time: O(n) - Space: O(1)

Sliding window

Subarrays

Given an array, a subarray is a contiguous section of the array. All the elements must be adjacent to each other in the original array and in their original order.

A subarray can be defined by two indices, the start and end. 

function fn(arr):
    left = 0
    for (int right = 0; right < arr.length; right++):
        Do some logic to "add" element at arr[right] to window

        while WINDOW_IS_INVALID:
            Do some logic to "remove" element at arr[left] from window
            left++

        Do some logic to update the answer

Complexity

Guarantee a maximum of 2n window iterations, each left/right pointer can move n times. If the logic for each window is O(1), then sliding window runs in O(n).

Even with while loop inside the for loop, complexity is still O(n) since the while loop can only iterate n times in total for the entire algorithm (left starts at 0, only increases, never exceeds n). If the while loop were run n times on one iteration of the for loop, it wouldn't run at all for all other iterations of the for loop.

Example 1 - Longest subarray with sum less than or equal to k

Problem Description - Easy

Given an array of positive integers nums and an integer k, find the length of the longest subarray whose sum is less than or equal to k.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def find_length(nums, k):
    # curr is the current sum of the window
    left = curr = ans = 0
    for right in range(len(nums)):
        curr += nums[right]
        while curr > k:
            curr -= nums[left]
            left += 1
        ans = max(ans, right - left + 1)

    return ans

Example 2 - Longest substring

Problem Description - Easy

You are given a binary string s (a string containing only "0" and "1"). You may choose up to one "0" and flip it to a "1". What is the length of the longest substring achievable that contains only "1"?

For example, given s = "1101100111", the answer is 5. If you perform the flip at index 2, the string becomes 1111100111.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# The problem equivalent to find the longest substring with at most once "0" => the condition is count("0") <= 1
def find_length(s):
    # curr is the current sum of the window
    left = curr = ans = 0
    for right in range(len(s)):
        if s[right] == "0":
            curr += 1
        while curr > 1:
            if s[left] == "0":
                curr -= 1
            left += 1
        ans = max(ans, right - left + 1)

    return ans

Number of subarrays

With a window (left, right). The number of valid windows end at index right equal to right -left + 1.

713. Subarray product less than k

Problem description - Medium

Given an array of positive integers nums and an integer k, return the number of subarrays where the product of all the elements in the subarray is strictly less than k.

For example, given the input nums = [10, 5, 2, 6], k = 100, the answer is 8. The subarrays with products less than k are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def number_of_subarrays(nums, k):
    # special case
    if k <= 1:
     return 0
    left  = ans = 0
    curr = 1
    for right in range(len(nums)):
        curr *= nums[right]
        while curr >= k:
            curr /= nums[left]
            left += 1
        ans += right - left + 1

    return ans

Fixed window size

function fn(arr, k):
    curr = some data to track the window

    // build the first window
    for (int i = 0; i < k; i++)
        Do something with curr or other variables to build first window

    ans = answer variable, probably equal to curr here depending on the problem
    for (int i = k; i < arr.length; i++)
        Add arr[i] to window
        Remove arr[i - k] from window
        Update ans

    return ans

Example 4 - largest sum of size k

Problem description - Medium

Given an integer array nums and an integer k, find the sum of the subarray with the largest sum whose length is k.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def number_of_subarrays(nums, k):
    curr = 0
    n = len(nums)
    for i in range(k):
        curr +=  nums[i]
    ans = curr
    for i in range(k, n):
        curr += nums[i] - nums[i-k]
        ans = max(ans, curr)

    return ans

643. Maximum Average Subarray I

Problem description - Easy

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value.

Any answer with a calculation error less than \(10^{-5}\) will be accepted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def max_average(nums, k):
    curr = 0
    n = len(nums)
    for i in range(k):
        curr +=  nums[i]/k
    ans = curr
    for i in range(k, n):
        curr += (nums[i] - nums[i-k])/k
        ans = max(ans, curr)

    return ans

1004. Max Consecutive Ones III

Problem description - Medium

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# The problem equivalent to find the longest subarray with at most k `0` => the condition is count(0) <= k
def max_consecutive_ones(nums, k):
    left = curr = ans = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            curr += 1
        while curr > k:
            if nums[left] == 0:
                curr -= 1
            left += 1
        ans = max(ans, right - left + 1)

    return ans

Prefix sum

Prefix sum is an array prefix where prefix[i] is the sum of all elements up to the index i (inclusive). For example, given nums = [5, 2, 1, 6, 3, 8], we would have prefix = [5, 7, 8, 14, 17, 25].

The sum of the subarray from i to j (inclusive) is prefix[j] - prefix[i - 1], or prefix[j] - prefix[i] + nums[i] if you don't want to deal with the out-of-bounds case when i = 0.

Given an array nums,

prefix = [nums[0]]
for (int i = 1; i < nums.length; i++)
    prefix.append(nums[i] + prefix[prefix.length - 1])

Example 1 - answer queries

Problem description - Easy

Given an integer array nums, an array queries where queries[i] = [x, y] and an integer limit, return a boolean array that represents the answer to each query. A query is true if the sum of the subarray from x to y is less than limit, or false otherwise.

For example, given nums = [1, 6, 3, 2, 7, 2], queries = [[0, 3], [2, 5], [2, 4]], and limit = 13, the answer is [true, false, true]. For each query, the subarray sums are [12, 14, 12].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def answer_queries(nums, queries, limit):
    prefix = [nums[0]]
    n = len(nums)
    for i in range(1, n):
        prefix.append(nums[i] + prefix[-1])
    ans = []
    for x, y in queries:
        ans.append(prefix[y] - prefix[x] + nums[x] < limit)

    return ans
# Space: O(n) to build prefix
# Time: O(n) to build prefix, O(m) to answer queries => O(n + m)

2270. Number of ways to split array

Problem description - Medium

Given an integer array nums, find the number of ways to split the array into two parts so that the first section has a sum greater than or equal to the sum of the second section. The second section should have at least one number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def count_split(nums):
    prefix = [nums[0]]
    n = len(nums)
    for i in range(1, n):
        prefix.append(nums[i] + prefix[-1])
    count = 0
    for i in range(n - 1):
        count += prefix[i] >= prefix[-1] - prefix[i]
    return count
# Space: O(n) to build prefix
# Time: O(n) to build prefix, O(n) to count => O(n + n)
Another way to improve space to O(1) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def count_split(nums):
    total = sum(nums)
    count = 0
    left = 0
    n = len(nums)
    for i in range(n - 1):
        left += nums[i]
        count += left >= total - left
    return count
# Space: O(1)
# Time: O(n) to calculate total, O(n) to count => O(n + n)

1480. Running Sum of 1d Array

Problem Description - Easy

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums

1
2
3
4
5
6
7
def running_sum(nums):
    ans = []
    curr_sum = 0
    for num in nums:
        curr_sum += num
        ans.append(curr_sum)        
    return ans

1413. Minimum Value to Get Positive Step by Step Sum

Problem description - Easy

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

def min_start_value(nums):
    ans = curr = 0
    for num in nums:
        curr += num
        ans = min(ans, curr)        
    return 1 - ans

2090. K Radius Subarray Averages

Problem description - Medium

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2

Solution 1 - Sliding window of fixed size - Space O(1)
def k_radius_subarray_avg(nums, k):
    # fixed window size of 2k+1
        curr = 0
        n = len(nums)
        ans = [-1] * n

        if k == 0:
            return nums

        if n < 2 * k + 1:
            return ans
        # Build the first window
        for i in range(2*k+1):
            curr +=  nums[i]
        ans[k] = curr//(2*k + 1)

        # Sliding window
        for i in range(2*k+1, n):
            curr += nums[i] - nums[i-(2*k+1)]
            ans[i-k] = curr//(2*k+1)

        return ans
Solution 2 - Prefix sum - Space O(n)
def k_radius_subarray_avg(nums, k):
    # fixed window size of 2k+1
    n = len(nums)
    ans = [-1] * n
    w = 2 * k + 1

    if k == 0:
        return nums

    if n < w:
        return ans
    # Build the prefix sum
    prefix = [nums[0]]
    for i in range(1,n):
        prefix.append(nums[i] + prefix[-1])

    for i in range(k, n-k):
        sum_window = prefix[i +k] - prefix[i-k] + nums[i-k]
        ans[i] = sum_window//w

    return ans
    # Time: O(n)
    # Space: O(n)