2702. Minimum Operations to Make Numbers Non-positive

HardArrayBinary Search
Leetcode Link

Problem Description

In this problem, we have an array of non-negative integers called nums and two positive integers x and y. We are allowed to perform operations on the array with the aim of reducing all the elements to zero or less. In each operation, we can choose an index i and decrease the element at that index nums[i] by x and simultaneously decrease all other elements by y. The task is to find and return the minimum number of such operations required to achieve the target condition where every element of the array is less than or equal to zero.

Intuition

To arrive at the solution, we need to recognize that decreasing all elements in the array besides the chosen index i by y in each operation will set a pace for how quickly the array can reach <= 0. This pace is constrained by the smallest element since it will hit zero first due to the decrement by y in each operation. The chosen element decremented by x will go down faster, so we want to figure out how often we need to 'hit' an element with the x decrement to bring it down to zero along with the rest of the elements.

A sound approach here is to perform a binary search on the number of operations t we would need since the answer will range between 0 and the maximum element in nums. For any guess t, we calculate if it's possible to bring all elements to less than or equal to zero within t operations. To do this, for each v in nums, we check if v > t * y, meaning the decay by y alone wouldn't be enough. If so, we need additional decrements of x - y to bring it down, which we calculate using ceil((v - t * y) / (x - y)). If the sum of additional decrements for all elements is less than or equal to t, we've found a viable candidate for the number of operations, and we can try to lower our guess. If not, we need to increase it. The first t that satisfies the condition for all elements in nums will be our answer.

This binary search loop continues until we narrow down the number of operations needed to a single value, which is then returned as the minimum number of operations required.

Learn more about Binary Search patterns.

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

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The solution uses a binary search algorithm to efficiently narrow down the minimum number of operations. The reasoning behind using binary search is that we're dealing with a monotonic condition: if we can bring down all elements to zero or less in t operations, we can also do it in t+1, t+2, etc. So, we try to find the smallest t for which the condition holds true.

Here are the steps of the implemented solution:

  1. Define an inner function check(t: int) -> bool that will verify if we can achieve the target with t operations. It performs the following steps:

    • Initialize a counter variable cnt to 0.
    • Loop through each element v in nums.
    • Within the loop, check if v is greater than t * y. If it is, calculate the extra decrements needed by subtracting t * y from v, and then dividing the rest by x - y using ceil. This ensures that we take into account the integer division rounding.
    • Increment cnt by the number computed. This represents the number of times x decrement should be applied to each element.
    • If the sum of decrements cnt is less than or equal to t, return True; otherwise return False.

  2. Conduct the binary search between l = 0 and r = max(nums), as the answer is in this range:

    • While l < r, calculate mid which is the midpoint of l and r.
    • Call check(mid) to verify if t = mid is a viable number of operations.
    • If check(mid) returns True, we can potentially reduce the number of operations, so set r to mid.
    • Else, if check(mid) returns False, we need more operations to reach the target, so set l to mid + 1.

  3. The loop ends when l is equal to r, meaning we've found the smallest possible t where check(t) is True. Return l as the minimum number of operations required.

The reason we use (l + r) >> 1 to calculate the midpoint is that it is equivalent to (l + r) / 2, but faster in terms of execution as it is a bit shift operation.

The time complexity of this solution is O(nlog(maxElement)), where n is the number of elements in nums. The log factor comes from the binary search, and for each step of the search, we iterate through the array once to check if the current t is viable. The space complexity is O(1) since we only use a few variables for the binary search and the checks.

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have an array nums = [3, 19, 10] and the integers x = 7 and y = 5.

The target condition is to reduce all elements to zero or less. According to the solution approach, we can perform a binary search to find the minimum number of operations, t.

Step by step, here's how the solution works with this example:

  1. We estimate the bounds [l, r] for the binary search. The upper bound r can be the maximum element in nums, which is 19. We start with l = 0.

  2. We define our check function, which will determine if a given number of operations t is sufficient to reduce all the elements in nums to zero or less.

  3. We begin the binary search. With l = 0 and r = 19, we calculate the midpoint mid to check. mid is (0 + 19) >> 1 = 9.

  4. We call check(9) to verify if t = 9 is a viable number of operations:

    • For nums[0] = 3, since 3 <= 9 * 5, we don't need any extra decrements because y decrements alone will bring it down to zero.
    • For nums[1] = 19, since 19 > 9 * 5, we do the math ceil((19 - 9 * 5) / (7 - 5)) = ceil((19 - 45) / 2) = ceil(-26 / 2) = 0. So no extra decrements are needed.
    • For nums[2] = 10, since 10 > 9 * 5, we do ceil((10 - 9 * 5) / (7 - 5)) = ceil((10 - 45) / 2) = ceil(-35 / 2) = 0.
    • Sum of extra decrements needed is 0 which is <= 9, so check(9) returns True.

  5. Since check(9) returns True, we can potentially reduce the number of operations. Now our new upper bound r is set to our current mid, which is 9. We repeat the binary search with new bounds l = 0 and r = 9 and find the midpoint again.

  6. After some iterations, we might find that lower values of t also pass the check function (in this example, t = 1 could also work since none of the elements need extra decrements). Binary search will continue until l == r.

  7. Once we find the smallest t such that check(t) is True, that will be our answer for the minimum number of operations required.

This detailed example walkthrough shows us how the binary search can efficiently find the minimum number of operations to reduce all array elements to zero or less. In this instance, given x and y are much larger than the array elements, even one operation is sufficient—hence the answer is t = 1.

Solution Implementation

1from math import ceil
2from typing import List
3
4class Solution:
5    def minOperations(self, nums: List[int], x: int, y: int) -> int:
6        # Helper function to check if the operation can be completed with 't' operations.
7        def is_possible_with_t_operations(t: int) -> bool:
8            # Initialize count of operations.
9            operations = 0
10            # Iterate through each number in the list.
11            for value in nums:
12                # If the value is greater than 't' times 'y', operations are needed.
13                if value > t * y:
14                    # Calculate the number of operations needed for the current value, and add to the total.
15                    operations += ceil((value - t * y) / (x - y))
16            # Return True if the counted operations are less than or equal to 't', else return False.
17            return operations <= t
18
19        # Initialize left and right pointers for the binary search.
20        left, right = 0, max(nums)
21        # Perform binary search to find the minimum number of operations required.
22        while left < right:
23            # Get the middle value between left and right.
24            mid = (left + right) >> 1  # Using bitwise shift to divide by 2.
25            # If the operation is possible with 'mid' operations, move the right boundary to 'mid'.
26            if is_possible_with_t_operations(mid):
27                right = mid
28            # Otherwise, move the left boundary past 'mid'.
29            else:
30                left = mid + 1
31        # The left pointer will now point to the minimum number of operations needed.
32        return left
33
1class Solution {
2    private int[] numbers;
3    private int x;
4    private int y;
5
6    // This method aims to find the minimum number of operations required.
7    // It uses a binary search approach to find the minimum 't'.
8    public int minOperations(int[] numbers, int x, int y) {
9        this.numbers = numbers;
10        this.x = x;
11        this.y = y;
12
13        // Initializing search range for 't'.
14        int left = 0;
15        int right = 0;
16      
17        // Find the largest number in the array to set the upper bound for 't'.
18        for (int value : numbers) {
19            right = Math.max(right, value);
20        }
21
22        // Perform binary search to find the minimum 't'.
23        while (left < right) {
24            int mid = (left + right) >>> 1;  // Calculate the mid value for 't'.
25            if (isFeasible(mid)) {
26                right = mid;  // Found new possible minimum, adjust right bound.
27            } else {
28                left = mid + 1;  // Target not feasible, adjust left bound.
29            }
30        }
31        return left;  // Return the minimum number of operations required.
32    }
33
34    // This helper method checks if it's possible to achieve the goal
35    // with 't' operations, where each operation reduces a number in the array by x until it's no smaller than t * y.
36    private boolean isFeasible(int target) {
37        long count = 0;  // Initialize the count of operations.
38
39        // Check each number in the array to see if operations are needed.
40        for (int value : numbers) {
41            if (value > (long) target * y) {
42                // Calculate operations required for current value and add to count.
43                count += (value - (long) target * y + x - y - 1) / (x - y);
44            }
45        }
46        // Check if the count of operations is less than or equal to target to meet the constraint.
47        return count <= target;
48    }
49}
50
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minOperations(std::vector<int>& nums, int increment, int decrement) {
7        // Using binary search to find the minimum number of operations
8        // Initialize the left (l) and right (r) boundaries for binary search
9        int left = 0, right = *std::max_element(nums.begin(), nums.end());
10      
11        // Lambda to check if a given number of operations (ops) is sufficient
12        auto isSufficient = [&](int ops) {
13            long long requiredOps = 0;
14            for (int value : nums) {
15                if (value > 1LL * ops * decrement) {
16                    // Calculate additional operations needed for this value
17                    requiredOps += (value - 1LL * ops * decrement + increment - decrement - 1) / (increment - decrement);
18                }
19            }
20            return requiredOps <= ops; // Return true if the total required operations are within the limit
21        };
22
23        // Binary search to find the minimum number of operations required
24        while (left < right) {
25            int mid = (left + right) >> 1; // Calculate the mid-point
26            if (isSufficient(mid)) {
27                right = mid; // If mid operations are sufficient, we look for a potential smaller number
28            } else {
29                left = mid + 1; // If mid operations are not sufficient, we need more operations
30            }
31        }
32
33        return left; // Once the search is narrowed down to a single element, left will be the minimum number of operations
34    }
35};
36
1function minOperations(nums: number[], x: number, y: number): number {
2    // Initialize pointers l and r for the binary search
3    let left = 0;
4    let right = Math.max(...nums);
5
6    // Define a check function that will return true if the operation is possible within t actions
7    const check = (threshold: number): boolean => {
8        // Initialize a counter for the number of operations performed
9        let operations = 0;
10
11        // Iterate over each value in the array
12        for (const value of nums) {
13            // If the value is greater than the threshold times y, calculate the necessary operations
14            if (value > threshold * y) {
15                // Add the ceil of the division to the operations' counter
16                operations += Math.ceil((value - threshold * y) / (x - y));
17            }
18        }
19
20        // Return true if the total operations are less than or equal to the threshold
21        return operations <= threshold;
22    };
23
24    // Use binary search to find the minimum number of operations to reach a certain state
25    while (left < right) {
26        // Find the mid-point of the current search range
27        const mid = (left + right) >> 1;
28
29        // If the current mid value satisfies the condition, adjust the right pointer
30        if (check(mid)) {
31            right = mid;
32        } else {
33            // Otherwise, adjust the left pointer
34            left = mid + 1;
35        }
36    }
37
38    // Return the minimum number of operations after binary search completes
39    return left;
40}
41
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

The given code snippet is implementing a binary search algorithm to find the minimum number of operations needed to reduce certain elements in the array nums so that no element is greater than t * y. To determine if a given target t is feasible, the check function is employed, which computes the number of operations needed for each element in nums. If the element is greater than t * y, the number of operations to reduce it is added to cnt.

The check function is called with a time complexity of O(n) where n is the number of elements in nums. This is because it iteratively checks each element once.

The binary search runs from 0 to the maximum value in nums. The time complexity for binary search is O(log m), where m is the range within which the binary search operates. Here m corresponds to the maximum value in nums.

The overall time complexity of the code is therefore O(n log m), since the binary search is the outer loop and the check function is called within each iteration of this binary search.

As for the space complexity, the space used is constant and does not depend on the input size, besides the input array itself. No additional data structures that grow with input size are created. Thus, the space complexity is O(1).

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

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

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 👨‍🏫