-3
\$\begingroup\$

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2.
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

What is the complexity of my solution?

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        int i=0,j=0;
        int sum=0;
        int res=Integer.MAX_VALUE;
        while(i<len && j<len)
        {
            if(sum<s)
            {
            sum = sum+nums[j];
            j++;
            }
            else
            {
               res = Math.min(res,j-i);
               sum = sum-nums[i];
                i++;

            }

        }
        while(sum>=s)
        {

                res = Math.min(res,j-i);
                sum = sum-nums[i];
                i++;

        }

        if(res == Integer.MAX_VALUE)
        return 0;
        else
        return res;
    }
}
\$\endgroup\$

closed as off-topic by πάντα ῥεῖ, 200_success, Ludisposed, t3chb0t, Sᴀᴍ Onᴇᴌᴀ Oct 15 '18 at 18:49

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "Authorship of code: Since Code Review is a community where programmers improve their skills through peer review, we require that the code be posted by an author or maintainer of the code, that the code be embedded directly, and that the poster know why the code is written the way it is." – 200_success, Sᴀᴍ Onᴇᴌᴀ
  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – πάντα ῥεῖ, Ludisposed, t3chb0t
If this question can be reworded to fit the rules in the help center, please edit the question.

0
\$\begingroup\$

The time complexity of this solution is O(n), i.e linear time complexity.

Explanation for time complexity to be linear : Here your loops are bounded by the variables i and j and one of them is always being incremented. So in worst case the loop can run only 2*len times.

\$\endgroup\$
  • \$\begingroup\$ Thanks, also since s is positive, sum>=s will always terminate before i can be negative. dont you think ? so i<len is not necessary \$\endgroup\$ – user182009 Oct 14 '18 at 22:39
  • \$\begingroup\$ My bad, updated the answer. \$\endgroup\$ – Apoorv Agarwal Oct 15 '18 at 2:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.