Minimum Value to Get Positive Step by Step Sum

🏠 ⬅️ ➡️

Given an array of integers nums, you start with an initial positive value startValue__.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2] Output: 5 Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1. step by step sum startValue = 4 | startValue = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -3 ) = 0 | (4 -3 ) = 1 | -3 (0 +4 ) = 4 | (1 +4 ) = 5 | 4 (4 +2 ) = 6 | (5 +2 ) = 7 | 2

Example 2:

Input: nums = [1,2] Output: 1 Explanation: Minimum start value should be positive.

Example 3:

Input: nums = [1,-2,-3] Output: 5

Constraints:

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program minStartValue
    implicit none

    integer, parameter :: dp = selected_real_kind(15)

    integer, dimension(:), allocatable :: nums
    integer :: n, i, j, startValue, stepByStepSum
    logical :: foundMin

    ! read input
    read(*,*) n
    allocate(nums(n))
    do i = 1, n
        read(*,*) nums(i)
    end do

    ! find minimum positive start value
    startValue = huge(startValue)
    foundMin = .false.
    do while (.not. foundMin)
        stepByStepSum = startValue
        do j = 1, n
            if (nums(j) < 0) then
                stepByStepSum = stepByStepSum + nums(j)
            else
                exit
            end if
        end do
        if (stepByStepSum >= 1) then
            foundMin = .true.
        else
            startValue = startValue - 1
        end if
    end do

    ! print result
    write(*,*) startValue

end program minStartValue
❌ Compiled
❌ Executed
❌ Correct 
module min_start_value
    implicit none
    private
    public :: min_start_value
contains
    function min_start_value(nums) result(min_value)
        integer, intent(in) :: nums(:)
        integer :: min_value
        integer :: start_value, step_sum
        integer :: i

        min_value = 1
        start_value = 1

        do i = 1, size(nums)
            step_sum = start_value + nums(i)
            if (step_sum < 1) then
                start_value = start_value + 1
            end if
        end do

        min_value = start_value
    end function min_start_value
end module min_start_value

program test_min_start_value
    use min_start_value
    implicit none
    integer, parameter :: nums(2) = [1, 2]
    integer :: min_value

    min_value = min_start_value(nums)

    write (*,*) "Minimum start value:", min_value
end program test_min_start_value
🌐 Data from online sources 
def maxSideLength(mat, threshold):
    m, n = len(mat), len(mat[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    ans = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = mat[i - 1][j - 1] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]
            k = ans + 1
            if i >= k and j >= k and dp[i][j] - dp[i][j - k] - dp[i - k][j] + dp[i - k][j - k] <= threshold:
                ans += 1

    return ans

We use dynamic programming to solve this problem. First, we create a 2D dp array of size (m+1) x (n+1) initialized with 0. The dp array stores the sum of all elements above and left of the current cell, including the current cell. Then, we iterate through each cell in the input matrix, and compute the sums for the dp array.

At each cell, we check if there is a possibility of extending the side length of the square. We do this by checking if the current cell's row and column are greater than or equal to the side length we are checking for (ans + 1). If true, we check if the sum of the square with side length (ans + 1) is less than or equal to the threshold. The sum is computed using the dp array's values by adding the top-left and bottom-right corners and subtracting the bottom-left and top-right corners. If the sum is within the threshold, we increment the ans variable.

Finally, we return the ans variable which stores the maximum side-length of a square with sum less than or equal to the threshold.

🌐 Data from online sources 
int maxSideLength(vector<vector<int>>& mat, int threshold) {
    int m = mat.size();
    int n = mat[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int ans = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = mat[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
            int k = ans + 1;
            if (i >= k && j >= k && dp[i][j] - dp[i][j-k] - dp[i-k][j] + dp[i-k][j-k] <= threshold) {
                ans++;
            }
        }
    }
    return ans;
}

We use dynamic programming to solve this problem. First, we create a 2D dp array of size (m+1) x (n+1) initialized with 0. The dp array stores the sum of all elements above and left of the current cell, including the current cell. Then, we iterate through each cell in the input matrix, and compute the sums for the dp array.

At each cell, we check if there is a possibility of extending the side length of the square. We do this by checking if the current cell's row and column are greater than or equal to the side length we are checking for (ans + 1). If true, we check if the sum of the square with side length (ans + 1) is less than or equal to the threshold. The sum is computed using the dp array's values by adding the top-left and bottom-right corners and subtracting the bottom-left and top-right corners. If the sum is within the threshold, we increment the ans variable.

Finally, we return the ans variable which stores the maximum side-length of a square with sum less than or equal to the threshold.