hard Maximum Score of a Good Subarray

Problem Statement

Given an array of positive integers nums (0-indexed) and an integer k, return the maximum possible score of a good subarray.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). If any subarray follows i <= k <= j condition, it is considered as good subarray.

Examples

Example 1:

• Input: nums = [1, 2, 3, 4, 5], k = 2
• Expected Output: 9
• Justification: The best subarray is [3, 4, 5], where the minimum value is 3, and the length is 3. The score is 3 * 3 = 9.

Example 2:

• Input: nums = [8, 1, 2, 4, 3], k = 3
• Expected Output: 6
• Justification: The best subarray is [2, 4, 3], where the minimum value is 2, and the length is 3. The score is 2 * 3 = 6.

Example 3:

• Input: nums = [4, 6, 4, 7, 2, 5, 1], k = 4
• Expected Output: 12
• Justification: The optimal subarray is [4, 6, 4, 7, 2, 5], with the minimum value 2 and length 6. Therefore, the score is 2 * 6 = 12.

Solution

To solve this problem, we start by considering the element at index k as the initial "good" subarray. Since the minimum value of a subarray containing only one element is the element itself, and the length is 1, the initial score is the value of nums[k]. We then expand this subarray to include adjacent elements on either side, continuously updating our calculation of the minimum value in the expanded subarray and its length. This process continues as long as expanding the subarray increases the score.

The key to this approach is to utilize a two-pointer technique, where we start with both pointers at k and expand outwards, ensuring that we always include k in our subarray. This ensures that all potential "good" subarrays are considered. The reason this method is effective is that it directly targets the constraint that k must always be within the subarray, allowing us to efficiently explore all relevant options without unnecessary comparisons or calculations.

Step-by-Step Algorithm

1. Initialize pointers and variables:

   • Start with two pointers left and right at the index k. This marks the beginning of the subarray to consider.
   • Initialize minVal to the value at index k in nums, since this is the only element in the current subarray.
   • Set maxScore also to the value at index k, as this is the score of the subarray consisting of only the kth element.

2. Expand the subarray:

   • Use a loop to expand the subarray to the left and right, as long as there are elements to consider (i.e., left > 0 or right < nums.length - 1).
   • Determine whether to move left or right based on boundary conditions and the values adjacent to the current subarray:
     • If left is at the start (0), only right can be moved.
     • If right is at the end (nums.length - 1), only left can be moved.
     • Otherwise, move the pointer (left or right) towards the side with the higher adjacent value to potentially increase the subarray's score.

3. Update minimum value and score:

   • After each expansion, update minVal to the minimum value in the new subarray. This involves comparing minVal with the new elements included in the subarray.
   • Calculate the score of the current subarray (minVal * (right - left + 1)) and update maxScore if this new score is higher than the current maxScore.

4. Repeat until fully expanded:

   • Continue expanding the subarray and updating the score until both left and right cannot be moved further (i.e., until the subarray spans the entire array).

5. Return the maximum score found:

   • Once the loop completes, return maxScore as the maximum possible score of a "good" subarray.

Algorithm Walkthrough

Let's consider the INput: nums = [4, 6, 4, 7, 2, 5, 1], k = 4

1. Initialization:

   • left = 4, right = 4, minVal = 2, maxScore = 2 (since nums[4] = 2).

2. First Expansion:

   • Can move both left and right (since neither are at the array's ends).
   • nums[3] = 7 (left of left) is greater than nums[5] = 5 (right of right), so move left to 3.
   • Update minVal to min(2, 7) = 2.
   • New score is 2 * (4 - 3 + 1) = 4. Update maxScore to 4.

3. Second Expansion:

   • Again, both left and right can move.
   • nums[2] = 4 (left of left) is less than nums[5] = 5, so move right to 5.
   • Update minVal to min(2, 5) = 2.
   • New score is 2 * (5 - 3 + 1) = 6. Update maxScore to 6.

4. Third Expansion:

   • Both left and right can still move.
   • nums[1] = 6 (left of left) is greater than nums[6] = 1 (right of right), so move left to 2.
   • Update minVal to min(2, 4) = 2.
   • New score is 2 * (5 - 2 + 1) = 8. Update maxScore to 8.

5. Fourth Expansion:

   • Both pointers can move.
   • nums[0] = 4 is greater than nums[6] = 1, so move left to 1.
   • Update minVal to min(2, 6) = 2.
   • New score is 2 * (5 - 1 + 1) = 10. Update maxScore to 10.

6. Fifth Expansion:

   • left can move (to 0), but right cannot (already at the end).
   • Move left to 0.
   • Update minVal to min(2, 4) = 2.
   • New score is 2 * (5 - 0 + 1) = 12. Update maxScore to 12.

7. Completion:

   • No further expansions are possible.
   • The loop ends, and the method returns maxScore = 12.

Code

class Solution {

  // Method to find the maximum score of a "good" subarray
  public int maximumScore(int[] nums, int k) {
    int left = k, right = k, minVal = nums[k];
    int maxScore = nums[k];
    while (left > 0 || right < nums.length - 1) {
      // If we can't move left, move right. If we can't move right, move left.
      // Otherwise, move towards the side with the higher value.
      if (left == 0) right++;
      else if (right == nums.length - 1) left--;
      else if (nums[left - 1] < nums[right + 1]) right++;
      else left--;

      // Update the minimum value in the current subarray
      minVal = Math.min(minVal, Math.min(nums[left], nums[right]));
      // Update the maxScore if possible
      maxScore = Math.max(maxScore, minVal * (right - left + 1));
    }
    return maxScore;
  }

  // Main method to test the algorithm with given examples
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.maximumScore(new int[] { 1, 2, 3, 4, 5 }, 2)); // Expected Output: 9
    // Example 2
    System.out.println(solution.maximumScore(new int[] { 8, 1, 2, 4, 3 }, 3)); // Expected Output: 6
    // Example 3
    System.out.println(
      solution.maximumScore(new int[] { 4, 6, 4, 7, 2, 5, 1 }, 4)
    ); // Expected Output: 12
  }
}

Complexity Analysis

Time Complexity:

• The time complexity of the solution is , where n is the number of elements in the input array nums. This is because, in the worst case, the algorithm expands the search space to include each element of the array once as it attempts to find the maximum score.

Space Complexity:

• The space complexity of the solution is , as the solution uses a fixed amount of additional space regardless of the input size. The extra space is used for the pointers and variables to store the current minimum value, current score, and maximum score found so far.