3010. Divide an Array Into Subarrays With Minimum Cost I

EasyArrayEnumerationSorting
Leetcode Link

Problem Description

In this problem, you are given an array of integers nums which has a length of n. Your task is to split this array into three disjoint contiguous subarrays. The term 'disjoint' means the subarrays should not overlap, and 'contiguous' indicates that the elements in each subarray should be next to each other in the original array nums.

The unique aspect of this problem is how the cost of a subarray is defined. The cost is determined by the first element of each subarray. So, if you create a subarray [2,5,6], the cost is 2 because it is the first element.

Your objective is to find a way to divide the array nums that results in the minimum possible sum of the costs of these three subarrays. Put simply, you want to select the first elements of three subarrays such that their sum is as small as possible.

Intuition

The solution draws on a straightforward idea: we need to find the smallest possible values for the first elements of three subarrays since these elements determine the cost of the subarrays.

Therefore, one element will be the first element of the whole array nums, which is unavoidable as it will always be the first element of the first subarray. Let's denote this element with the variable a.

For the other two subarrays, we need to find the smallest and second smallest values among the remaining elements of nums. We don't worry about the specific position within the array of these elements because our objective is to minimize the sum of the three costs, not to arrange subarrays in any particular order.

The solution's approach begins by initializing a to the first element of nums. We then iterate through the rest of the array looking for the smallest (b) and second smallest (c) elements. If we encounter a value less than b, we shift the old b to c and update b with this new smallest value. Otherwise, if we find a value that is less than c but greater than or equal to b, we just update c since we have found a new second smallest value.

Finally, we add a, b, and c together to get the minimum possible sum of the costs, as this sum represents the cost of the first element of each of the three needed subarrays.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The algorithm relies on the notion of finding the minimum and second minimum values in an array. This is a common pattern when dealing with problems that require optimization based on certain criteria—in this case, the minimum sum of specific elements.

In the reference solution approach, the variables a, b, and c represent the first element of the array, the smallest value, and the second smallest value among the remaining elements of the array, respectively. The inf or infinity value used to initialize b and c ensures that any real number encountered in the nums array will be less than inf and appropriately assigned to b or c.

The process to achieve the solution can be broken into the following steps:

  1. Initialize variables a, b, and c:

    • a is set to nums[0], because it will be the first element of the first subarray and its cost is unavoidable.
    • b and c are set to infinity (inf).

  2. Loop through the nums array starting from the second element, as the first is already used for a.

  3. For each element x in nums:

    • If x is less than b, it means we have found a new minimum. Hence, we update c to the old b (the previous minimum), then update b to x (the new minimum).
    • Otherwise, if x is greater than or equal to b but less than c, we just need to update c to x, as we have found a new second smallest value.

  4. Once the loop is completed, a, b, and c will hold the cost of the first elements of the three subarrays, with a being the cost of the unavoidable first subarray, and b and c being the minimum and second minimum costs we could find for the other two subarrays.

By the end of the iteration, adding a, b, and c gives us the minimum possible sum for the costs of the three subarrays.

The beauty of this solution lies in its simplicity and efficiency. It allows us to find the minimum sum of costs with just one pass through the array and without any need for complex data structures or sorting algorithms. This single-pass scan of the array also means that the solution has a time complexity of O(n), where n is the number of elements in nums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the array nums = [4, 1, 3, 2, 5].

  1. Initialize a, b, c:

    • a is set to nums[0], so a = 4.
    • b and c are set to infinity, and thus any number from the array will replace these values.

  2. Loop through the nums array starting from the second element, nums[1].

  3. Iterating through nums:

    • Current element is 1. Since 1 < inf, we update b:

      • b now becomes 4 (old b) and we update b to 1.

    • Now a = 4, b = 1, c = 4.

    • Next element is 3. Since 3 > b (1) but 3 < c (4), we update c:

      • Hence, c is now 3.

    • Now a = 4, b = 1, c = 3.

    • Next comes 2. It is less than c (3) and also less than b (1):

      • Since 2 is not less than b, we only update c with 2.

    • Now a = 4, b = 1, c = 2.

    • The last element is 5. It is greater than both b and c, so no update is made.

    • The values remain a = 4, b = 1, c = 2.

  4. By the end of the iteration, we have a = 4 (the cost of the first subarray), b = 1, and c = 2. The latter two are the minimum and second minimum values that could be the costs of the other two subarrays.

The minimum possible sum of the costs for the three subarrays is the sum of a, b, and c, which in this case is (4 + 1 + 2 = 7).

So by employing a single pass through the array and maintaining two variables to keep track of the smallest and second smallest elements after the first, we are able to efficiently compute the minimum sum of subarray costs.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minimumCost(self, nums: List[int]) -> int:
6        # Initialize variables. 'a' will hold the smallest number, 
7        # 'b' will be second smallest, 'c' will be the third smallest.
8        # 'inf' is used to represent an infinitely large number.
9        a, b, c = nums[0], inf, inf
10      
11        # Iterate over the nums list starting from the second element.
12        for num in nums[1:]:
13            # If the current number is smaller than 'b', 
14            # then we update 'b' and 'c' accordingly.
15            if num < b:
16                # Before updating 'b', shift its value to 'c'.
17                c = b
18                b = num
19            # If 'num' is not smaller than 'b', but is less than 'c', 
20            # then we just update 'c'.
21            elif num < c:
22                c = num
23      
24        # Return the sum of the three smallest numbers.
25        return a + b + c
26
27# Note: Calling the method minimumCost will require an instance of the Solution class.
28# For example: Solution().minimumCost([your_list_of_numbers])
29
1class Solution {
2    public int minimumCost(int[] prices) {
3        // Initialize variables for the smallest, second smallest, and third smallest prices
4        int smallest = prices[0], secondSmallest = Integer.MAX_VALUE, thirdSmallest = Integer.MAX_VALUE;
5      
6        // Iterate through the prices starting from the second element
7        for (int i = 1; i < prices.length; ++i) {
8            // Check if the current price is less than the second smallest
9            if (prices[i] < secondSmallest) {
10                // Update the third smallest to be the previous second smallest
11                thirdSmallest = secondSmallest;
12                // Update the second smallest to be the current price
13                secondSmallest = prices[i];
14            } else if (prices[i] < thirdSmallest) { // Otherwise, check if the current price is less than the third smallest
15                // Update the third smallest to be the current price
16                thirdSmallest = prices[i];
17            }
18        }
19
20        // Return the sum of smallest, second smallest, and third smallest prices
21        return smallest + secondSmallest + thirdSmallest;
22    }
23}
24
1#include <vector>
2#include <algorithm> // For sort
3
4class Solution {
5public:
6    int minimumCost(std::vector<int>& nums) {
7        // Check if the vector has less than three numbers;
8        // if it does, one cannot select three numbers, so return 0.
9        if(nums.size() < 3) {
10            return 0;
11        }
12      
13        // Sort the nums vector in ascending order.
14        std::sort(nums.begin(), nums.end());
15
16        // Initialize the sum of the first three smallest numbers.
17        int minimumSum = nums[0] + nums[1] + nums[2];
18
19        // Return the sum, which is the cost of purchasing the three cheapest items.
20        return minimumSum;
21    }
22};
23
1function minimumCost(nums: number[]): number {
2    // Initialize the smallest elements a, b, and c with the first element and two placeholders (100).
3    let smallest = nums[0];
4    let secondSmallest = 100;
5    let thirdSmallest = 100;
6  
7    // Iterate over the array of numbers starting from the second element.
8    for (const current of nums.slice(1)) {
9        // If the current element is smaller than the second smallest, update the second and third smallest.
10        if (current < secondSmallest) {
11            [secondSmallest, thirdSmallest] = [current, secondSmallest];
12        } else if (current < thirdSmallest) {
13            // If the current element is only smaller than the third smallest, only update the third smallest.
14            thirdSmallest = current;
15        }
16    }
17  
18    // Sum the three smallest elements found.
19    return smallest + secondSmallest + thirdSmallest;
20}
21
Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Time and Space Complexity

The provided Python code aims to calculate the minimum cost by finding the three smallest numbers in the given list nums and summing them up. It initializes a with the first element of the list and sets b and c to infinity (inf). The loop then iterates through the remaining elements, updating b and c with the next smallest values.

The time complexity of this code is indeed O(n) where n is the length of the array nums. This is because the code goes through the elements of nums exactly once in a single loop, performing a constant number of operations per element (comparisons and assignments).

The space complexity of the code is O(1) as the space used does not grow with the size of the input list nums. Only a fixed number of variables (a, b, c) are used regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫