Facebook Coding Interview Question-FindLongestSubarrayBySum

Problem Statement

Given an unsorted array of integers, find a subarray which adds to a given number

arr = [10,2,-2,-20,10]
sum = -10

The longest subarray is [10,2,-2,-20] having the length of 4.The solution should return the starting and end indices of the found subarray, here 0,3

Expected Result - 0,3

Naive Implementation

Find out all the subarrays whose sum computes to given sum S.Then,it will check the sum of each subarray with the given sum S and return the indices of the longest subarray. But this approach takes O(n^2) time complexity which is generally considered bad.

Efficient Implementation - Efficient way of doing this is using a HashMap

Time Complexity - O(n) // Much better than O(n^2)
Space Complexity - O(n)

import java.util.*;
import java.lang.*;
import java.io.*;


public class MaxLengthSubArray
{
    public static void main (String[] args) throws java.lang.Exception
    {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = new int[]{10,2,-2,-20,10};
        int total= -10;

        // create a `HashMap` to store all the array elements `sum` and their 
        // `indices`
        Map<Integer, Integer> map=new HashMap<>();
        map.put(0,-1);

        // we have to keep track of the sum of the subArrays,so that is stored in 
        // this variable `sum` ie `sum` is the current sum
        int sum=0;

        //starting index pointing to the first element of the array 
        int start=0;

        // end is not pointing anything,so it is set to `-1`
        int end=-1;

        // Traverse through the entire array and calculate the current  
        // `sum`.After calculating the currentSum,we will subtract the currentSum 
        // with the  given `sum S` and check whether it is equal to 0.If, it is 
        // equal to `0` then that means we have found the subArray which will 
        //give sum S = -10
        for(int i=0;i<a.length;i++){
        sum+=a[i];
        if(!map.containsKey(sum))
        map.put(sum,i);

        if(map.containsKey(sum-total ) && start<i - map.get(sum-total )){
            start= i-map.get(sum-total );
            end=i;
            }
        }

        System.out.println(end-start+1+" "+end);

    }

}

If you found this article helpful, please tap the Follow this channel for more articles on data strucures and algorithms.