Longest Subarray

Array, Dynamic Sliding Window

Finds the longest subarray with sum less than or equal to k in an array.

Solutions

Approach -Brute Force Technique

Steps

1. Initialize Variables: The algorithm starts by initializing a variable maxLength to 0. This will keep track of the length of the longest subarray found so far.

2. Iterate Over Array: The algorithm then enters a nested loop that iterates over each possible subarray in nums.

   • Calculate Subarray Sum: For each subarray, the algorithm calculates the sum of the elements in the subarray.

   • Check for Desired Sum: If the sum of the elements in the subarray is less than or equal to k, the algorithm updates maxLength to be the maximum of maxLength and the length of the current subarray.

3. Return Result: After the loops, the algorithm returns maxLength, which is the length of the longest subarray with a sum that does not exceed k.

public class Solution {
    public int LongestSubarray(int[] nums, int k) {
        int maxLength = 0;
        for (int start = 0; start < nums.Length; start++) {
            int sum = 0;
            for (int end = start; end < nums.Length; end++) {
                sum += nums[end];
                if (sum <= k) {
                    maxLength = Math.Max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }
}

Complexity

• Time complexity: O(N^2)

• Space complexity: O(1)

Approach - Dynamic Sliding Window

This program uses two pointers, start and end, to represent the current subarray. It moves end forward and adds arr[end] to sum . If sum becomes more than k, it removes elements from the start until sum is less than or equal to k. The maximum length of the subarrays encountered is the answer.

Steps

1. Initialize Variables: The algorithm starts by initializing several variables: start and end to keep track of the current subarray, sum to keep track of the sum of the current subarray, and maxLength to keep track of the length of the longest subarray found so far.

2. Iterate Over Array: The algorithm then enters a loop that iterates over each element in the input array arr.

   • Update Sum: For each element, the algorithm adds the element’s value to sum.

   • Adjust Start of Subarray: If sum exceeds k, the algorithm enters a loop that removes elements from the start of the subarray until sum is less than or equal to k.

   • Update maxLength: If sum is less than or equal to k, the algorithm updates maxLength to be the maximum of maxLength and the length of the current subarray.

   • Move End of Subarray: The algorithm then increments end to move to the next element in the array.

3. Return Result: After the loop, the algorithm returns maxLength, which is the length of the longest subarray with a sum that does not exceed k.

public class Program
{

     int LongestSubarray(int[] arr, int k)
    {
        int n = arr.Length;
        int start = 0, end = 0;
        int sum = 0, maxLength = 0;

        while (end < n)
        {
            // Add current element to sum
            sum += arr[end];

            // If sum is more than k, remove elements from the start
            while (sum > k && start < n)
            {
                sum -= arr[start];
                start++;
            }

            // Update maxLength if needed
            if (sum <= k)
            {
                maxLength = Math.Max(maxLength, end - start + 1);
            }

            // Move end forward
            end++;
        }

        return maxLength;
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(1)