0

I have a vector<int> num, I want to get the size of longest subarray with the sum less than or equal to k.

My approach: O(n^2). Repeat for every element in the array.

Can we do better?'

Note: I don't need the actual longest subarray, only its size. So the return value is int.

1
  • Can the elements be negative? Oct 23, 2016 at 3:11

1 Answer 1

1

Assuming, that the vector contains only non-negative integers:

int getLargestSubsequenceSize(vector<int>& myVector, int k){

    int maxCount = 0;
    int i=0,j=0;
    int sum = 0;

    while(j < myVector.size()){

         sum += myVector[j];
         if(sum > k){
              int currCount = j-i;
              if(currCount > maxCount)
                  maxCount = currCount;
              sum -= myVector[i];
              i++;
         } 
         j++;
    }
    return maxCount;
}

The above function has two indexes (i,j). j will increment and add current number to the sum until sum becomes greater than k. Once it is greater, we will calculate the length of this sub-sequence and check whether it is bigger than previous subsequence. If yes, we will update the maxCount. Now, we will increment the lower index (i) and repeat the process. Time Complexity = O(n)

1
  • 2
    Explain how this works, and why it's better than O(n^2) Oct 23, 2016 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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