Start learning free

LESSON 452 OF 541 · DYNAMIC PROGRAMMING

Maximum Product Subarray in Swift: O(n) Time, O(1) Space

Practice O(n) Read the full explanation

Given an array of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

  • 1 <= nums.count <= 105
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 9
    Ctrl + Enter to check

    SWIFT · DYNAMIC PROGRAMMING

    Maximum Product Subarray in Swift, explained

    Problem overview

    maxProduct receives an array of integers, nums, and returns the largest product of a subarray: one or more elements that stand next to each other. The elements range from -10 to 10, so there are negatives and zeros to handle.

    For [2, 3, -2, 4] the answer is 6, from [2, 3]: the -2 makes every subarray that contains it negative. For [-2, 0, -1] the answer is 0: the two negatives would give 2, but they aren't next to each other, because the 0 stands between them. For [-2, 3, -4] the answer is 24, the whole array, since the two negatives cancel.

    Approach: track the largest and the smallest product

    Trying every subarray takes O(n²) time or worse. A single pass is enough if, at each position, we know the best subarray that ends there. For sums, the largest sum ending at i is all you need. For products it isn't, because a negative number flips the order: the most negative product so far becomes the most positive after multiplying by a negative element.

    So the pass keeps two numbers for the subarrays ending at the current element: maxHere, the largest product, and minHere, the smallest. At a negative element, the two swap roles before being multiplied. Each of them is then either the element alone, which starts a fresh subarray (and is how a product gets past a 0), or the old value times the element. A third variable, result, remembers the largest maxHere seen.

    The trace for [2, 3, -2, 4], starting with all three variables at 2:

    inums[i]maxHereminHereresult
    13636
    2-2-2-126
    344-486

    For [-2, 3, -4], starting with all three at -2:

    inums[i]maxHereminHereresult
    133-63
    2-424-1224

    At the last element, the -4 swaps the two values, so maxHere becomes -6, and -6 times -4 is 24.

    Step by step

    1. maxHere. A var starting at nums[0]: at the first element, the only subarray ending there is the element itself.
    2. minHere. Also starting at nums[0].
    3. result. Also nums[0]. A subarray needs at least one element, so even a negative first element is a valid starting answer.
    4. Loop i over 1..<nums.count, since element 0 is already counted.
    5. Negative element. If nums[i] < 0, swap maxHere and minHere with one tuple assignment. Afterwards each is the right one to multiply.
    6. Update maxHere to the larger of nums[i] and maxHere * nums[i].
    7. Update minHere to the smaller of nums[i] and minHere * nums[i].
    8. Update result to the larger of result and maxHere.
    9. Return result.

    The solution in Swift

    class Solution {

    func maxProduct(_ nums: [Int]) -> Int {
        var maxHere = nums[0]
        var minHere = nums[0]
        var result = nums[0]
        for i in 1..<nums.count {
            if nums[i] < 0 {
                (maxHere, minHere) = (minHere, maxHere)
            }
            maxHere = max(nums[i], maxHere * nums[i])
            minHere = min(nums[i], minHere * nums[i])
            result = max(result, maxHere)
        }
        return result
    }
}

    The Swift details worth a closer look:

    • Swapping with a tuple. (maxHere, minHere) = (minHere, maxHere) builds a pair from the right side first and then unpacks it into the left side, so no temporary variable is needed. Both names must be var.
    • The global max and min. They are free functions that take two values.
    • Order of the updates. minHere is computed from the old minHere, not from the new maxHere, so the two lines are independent. Both read the value after the swap.
    • Ranges and the single element. 1..<nums.count is empty when the array has one element, so [-3] returns -3. An empty array would crash on nums[0] (and 1..<0 isn't a valid range); the lesson guarantees at least one element.
    • Overflow. Int is 64 bits in Swift, and overflowing arithmetic crashes the program instead of wrapping. The lesson promises that every subarray product fits in 32 bits, so the products here stay small.

    Complexity

    Time: O(n). One pass, with a constant amount of work for each element.

    Space: O(1). Three integers, whatever the length of the array.

    Edge cases and common mistakes

    • Tracking only the maximum. With only maxHere, the array [-2, 3, -4] would give 3 instead of 24, since the -6 that the second negative needs would be lost.
    • Zeros. A 0 sends both products to 0 through max(nums[i], ...) and min(nums[i], ...), and the next element starts a new subarray. [-2, 0, -1] gives 0, and [0, 2] gives 2.
    • A single negative number. [-3] gives -3, not 0. Starting result at 0 would be a mistake.
    • All negatives. [-2, -3, -4] gives 12 (the last two elements), and [-1, -1] gives 1.
    • Forgetting to swap before multiplying. The multiplication would use the wrong extreme for a negative element.
    • Not allowing a fresh start. Using only maxHere * nums[i] would let a product that has gone to 0 or below drag every later subarray down. Comparing with nums[i] alone lets the pass start over at any element.
    • Looking for the best at the end only. The best subarray can end anywhere, not only at the last element, so result is updated in every round. In [2, 3, -2, 4] the best product is already 6 after the second element and stays so.

    Testing

    • [2, 3, -2, 4] gives 6.
    • [-2, 0, -1] gives 0.
    • [-2, 3, -4] gives 24.
    • [-3] gives -3, and [0] gives 0.
    • [-2, -3, -4] gives 12.
    • [-1, -1] gives 1.
    • [3, -1, 4] gives 4.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free