Longest Sub Array

Question

Can anyone suggest a simple solution for the below question.

Longest Sub-array: Find the length of longest contiguous sub-array where the sum of the elements in subarray is less than or equal to "k".

Inputs are: array and k.

Example:

Array = {1,2,3}, k = 3

Output:

2

Explanation:

Sub arrays : {1},{2},{3},{1,2},{2,3},{1,2,3}

{1,2} => max length = 2; 1+2 = 3 (<=k);

Answer 1

an O(n) approach. In high level:

Have 2 pointers start and end, start being the start of subarray, end being end (exclusive). An int sum to keep the subarray sum. An int len to keep subarray len.

Have both set to position 0.

1. Keep moving the end pointer by:

   while (end < arr.length && sum + arr[end] <= k) {
       sum += arr[end];
       end ++;
   }
   if ((end - start) > len ) {
     len = (end-start);
   }
   

   Which will find you the longest subarray with sum < k with start with start

2. Move start

   sum -= arr[start];
   start++;
   

3. Go back to 1, until end passed the last element of array

At the end you will find the max length (stored in len)

Leave handling of some edge-cases to you (e.g. if there is an element in array with value > k. etc)

Answer 2

The easiest and naive answer is to traverse your array and find the longest subarray starting at the current index.

int[] a = { 1,2,3,1,1,2,3,1,3 };
int k = 4;

int best_i = 0; // from index
int best_j = 0; // to index, so best length = j - i + 1
int best_sum = 0;

for (int i = 0; i < a.length; i++) { // starting index from beginning to end 
    int sum = 0;
    for (int j = i; j < a.length; j++) { // ending index from current to end
        sum += a[j];
        if (sum > k) break;
        if (j - i > best_j - best_i) { // best length found
            best_i = i;
            best_j = j;
            best_sum = sum;
        }
    }
}

System.out.println("best length = " + (best_j - best_i + 1) + " (indexes " + best_i + ".." + best_j + "), sum = " + best_sum);
// best length = 3 (indexes 3..5), sum = 4

Answer 3

An efficient method is to use dynamic programming, to reduce the number of summation operations. For example, if you sum (1 + 2) = 3, you don't wanna sum (1 + 2 + 3) = 6 again, you only wanna sum (3 + 3) = 6 (where the first 3 has already been calculated and saved into a hashmap). In this solution, the hashmap represents the sum from index i to index j, in the format <i, <j, sum>>. So you have all sums starting from index i stored in the inner hashmap. Note that you could also use a 2D array instead of the nested hashmap structure, but for very large data, you are likely to get an out-of-memory exception while initializing that array.

    static int maxLength(int[] a, int k) {
        Map<Integer, Map<Integer, Long>> map = new HashMap<Integer, Map<Integer, Long>>();

        int maxLength = 0;
        for(int i = 0; i < a.length - 1; i++) {
            Map<Integer, Long> map2 = new HashMap<Integer, Long>();
            map2.put(i, (long)a[i]);
            map.put(i, map2);
            if(a[i] == k) {
                maxLength = 1;
            }
        }

        for(int l = 2; l <= a.length; l++) {
            long sum = 0;
            for(int i = 0; i <= a.length - l; i++) {
                int j = i + l - 1;
                Map<Integer, Long> map2 = map.get(i);
                sum = map2.get(j - 1) + a[j];
                map2.put(j, sum);

                if(sum <= k) {
                    if(l > maxLength) {
                        maxLength = l;
                    }
                }
            }
        }

        return maxLength;
    }

Answer 4

Python Implementation

Time complexity O(n)

No additional space needed

def longest_sub_array_sum(input_array: list, k: int) -> int:
    longest_size = 0
    
    if input_array:
        i = 0
        j = 1
        longest_size = 0 if input_array[i] != k else 1
        current_sum = input_array[i]
        
        while j < len(input_array):
            if current_sum <= k:
                if j - i > longest_size:
                    longest_size = j - i
                current_sum += input_array[j]
                j += 1

            elif current_sum > k:
                current_sum -= input_array[i]
                i += 1
                
    return longest_size

Answer 5

Here I am using only on for loop, but I have my doubt on the complexity of this solution, is it O(n) or O(n2). Seems like one for loop but I don't think a number of operation are less than brute force or two for loop.

function maxLength(a, k) {

var maxLen = 0;
var currMaxLen = 0;
var currSum = 0;
var currIndex = 0;

for(index = 0; index < a.length; index++){
    currSum = currSum + a[index];

    if(currSum <= k){
        currMaxLen++;
    } else{
        //reset
        index = currIndex;
        currIndex++;
        maxLen = Math.max(maxLen, currMaxLen);
        currSum = 0;
        currMaxLen = 0;
    }
}
maxLen = Math.max(maxLen, currMaxLen);
return maxLen;

}