We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Divide an Array Into Subarrays With Minimum Cost I

Number: 3263

Difficulty: Easy

Paid? No

Companies: American Express

Problem Description

Given an array of integers, the task is to divide the array into 3 disjoint contiguous subarrays. The cost of a subarray is defined as its first element. The goal is to determine the minimum possible sum of these costs.

Key Insights

  • The array must be split into exactly 3 contiguous parts, meaning you need to select 2 split points.
  • The cost for a subarray is only determined by its first element.
  • The first element of the entire array automatically contributes to the cost.
  • By choosing two indices (split positions), the cost becomes: nums[0] + nums[i] + nums[j], where i and j are the starting indices of the second and third subarrays respectively.
  • Given the small constraints (n <= 50), iterating over all possible split points using a nested loop is efficient.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

We can solve the problem by iterating through all possible ways to choose two breakpoints in the array. For each valid pair of breakpoints (i, j) where 0 < i < j < n, compute the total cost as nums[0] + nums[i] + nums[j]. Track the minimum cost found over all iterations.

Code Solutions

# Python solution with detailed comments

def minCost(nums):
    n = len(nums)
    # Initialize the minimum cost with a large number
    min_cost = float('inf')
    
    # Iterate over the first split point (i represents the start of the second subarray)
    for i in range(1, n - 1):
        # Iterate over the second split point (j represents the start of the third subarray)
        for j in range(i + 1, n):
            # Calculate cost: the first element of each subarray
            cost = nums[0] + nums[i] + nums[j]
            # Update minimum cost if a lower sum is found
            min_cost = min(min_cost, cost)
    
    return min_cost

# Example usage:
print(minCost([1,2,3,12]))  # Expected output: 6
← Back to All Questions