Current online judgement provides wrong answers for some cases; My O(n) and O(nlogn) solutions


  • 0

    The current online judgement didn't consider the potential integer overflow problem when calculating the subarray sum.
    Below are some test case examples that the online judgement provides wrong answers:

    • input:
      7
      [1,2147483647,6]
      output should be 1 while it's 0
    • intput :
      7
      [1,6,2147483647]
      output should be 1 while it's 2
    • input:
      2147483647
      [2,2147483646,1]
      output should be 2 while it's 0
    • input:
      2147483647
      [1,2147483645,2]
      output should be 2 while it's 0

    To get right answer, the variable sum should be long type instead of int.

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int result = Integer.MAX_VALUE;
            long sum = 0;
            int i = 0, j = 0;
            while (j < nums.length) {
                sum += nums[j++];
                while (sum >= s) {
                    result = Math.min(result, j - i);
                    sum -= nums[i++];
                }
            }
            // the result can't be equal to Integer.MAX_VALUE, 
            // because the maximum array length in Java is smaller than Integer.MAX_VALUE
            return result == Integer.MAX_VALUE ? 0 : result;
        }
    }
    

    If we're not supposed to use long type, we can use the following solution:

    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int result = Integer.MAX_VALUE;
            int sum = 0;
            int i = 0, j = 0;
            while (j < nums.length) {
                int newSum = sum + nums[j++];
                if (newSum <= 0) {    // integer overflow
                    // cancel the current step and move pointer i forward
                    j--;
                    sum -= nums[i++];
                } else {
                    sum = newSum;
                    while (sum >= s) {
                        result = Math.min(result, j - i);
                        sum -= nums[i++];
                    }
                }
            }
            return result == Integer.MAX_VALUE ? 0 : result;
        }
    }
    

    Above are two O(n) solutions with two pointers. Below are two binary search solutions run in O(nlogn).

    • binary search solution 1:
    /**
     * Calculate the accumulative sum of array nums, then the sum of subarray nums[i:j] should be sums[j] - sums[i - 1].
     Iterate through all possible start index of target subarray, and use binary search to find the corresponding minimum end index.
     */
    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int result = Integer.MAX_VALUE;
            int[] sums = new int[nums.length];//
            for (int i = 0; i < sums.length; i++) {
                sums[i] = (i == 0 ? 0 : sums[i - 1]) + nums[i];
            }
            for (int i = 0; i < sums.length; i++) {
                int l = i, r = sums.length;
                int target = s + (l == 0 ? 0 : sums[l - 1]); //
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (sums[mid] < target) l = mid + 1;
                    else r = mid;
                }
                if (l == sums.length) break;    // sum of nums[i:nums.length-1] is smaller than s
                result = Math.min(result, l - i + 1);
            }
            return result == Integer.MAX_VALUE ? 0 : result;
        }
    }
    
    • binary search solution 2:
    /**
     * The possible length is in range [0:n], use binary search to check 
     whether there exists a subarray with length `mid` and has sum >= s.
     If no, there's no subarray with length than `mid` satisfy the condition as well.
     */
    public class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int result = 0;
            int l = 1, r = nums.length;    // l starts from 1 because our target is subarray of minimum positive length
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (existSubArray(s, nums, mid)) {
                    result = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return result;
        }
        // check if there exists a subarray of length k that has sum >= s
        private boolean existSubArray(int s, int[] nums, int size) {//
            int sum = 0;//
            for (int i = 0; i < nums.length; i++) {
                if (i >= size) sum -= nums[i - size];
                sum += nums[i];
                if (sum >= s) return true;
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.