How to find the subarray that has sum closest to zero or a certain value t in O(nlogn)


  • 4
    P

    Given an array A[] of integers(positive and nonpositive), how can you find a continuous subarray of A[] whose sum is closest to 0? Or closest to a certain value t?


  • 1
    void findSubArraySumCloseToT() {
    		// -50, -10, 10, 24, 54, 83, 100 
    		int[] a = new int[] {10, 24, 55, -10, -50, 54, 83, 100};
    		int t = 53;
    		int sum = 0, wldPLaceAfterThis = -1;
    		boolean exactSum = false;
    		
    		// try to find exact sum equals t in the array
    		// this will be O(n) if there is an exact match
    		// we could skip this part and modify the code after that to
    		// look for exact match too, but this will do it in O(n) if it exist
                    // without the need to sort (O(nlogn))
    		Map<Integer, Integer> map = new HashMap<>();
    		int cs = 0;
    		for(int i = 0; i < a.length; i++) {
    			cs += a[i];
    			if(cs == t) {
    				System.out.println(0 + " " + i);
    				exactSum = true;
    				break;
    			}
    			if(map.containsKey(cs - t)) {
    				System.out.println(map.get(cs - t) + 1 + " " + i);
    				exactSum = true;
    				break;
    			}
    			
    			map.put(cs, i);
    		}
    		
    		// if no continuous subarray has the exact sum equals to t 
    		if(!exactSum) {
    			// hashtable to map from element new index position in the sorted array and
    			// its original index in the input array
    			// we can achive this by implementing quick sort and in the partition step when
    			// we pick the pivot and place it in its sorted position populate the map
    			Map<Integer, Integer> indexMap = new HashMap<>();
    			// I did not do this here so the result indexes will be from the sorted array
    			Arrays.sort(a);
    			// calculate the whole array sum
    			// calculate where would we place t if it will be in the array
    			for(int i = 0; i < a.length; i++) {
    				sum += a[i];
    				if(i > 0 && a[i] > t && a[i - 1] < t)
    					wldPLaceAfterThis = i - 1;
    			}
    			
    			if(t >= sum)
    				System.out.println("subarray = " + 0 + ", " + (a.length - 1));
    			else if(t < a[0])
    				System.out.println("can't find solution");
    			else {
    				// starting from the first element that is smaller than t in the array
    				// starting summing from this element till the array start
    				// if the previous element will make the sum larger but still < t then it is part of the solution
    				// else you are done, all the rest of these numbers will not contribute to the solution, these
    				// elements will make us further to t than closer to it, this happens when  you start decrementing the
    				// running sum because of negative numbers for example
    				sum = a[wldPLaceAfterThis];
    				int i = wldPLaceAfterThis - 1;
    				for(; i >= 0; i--) {
    					if(sum + a[i] >= sum && sum + a[i] < t)
    						sum += a[i];
    					else
    						break;
    				}
    //				System.out.println("subarray = " + indexMap.get(i + 1) + ", " + indexMap.get(wldPLaceAfterThis));
    				System.out.println("subarray = " + (i + 1) + ", " + wldPLaceAfterThis);
    			}
    		}
    	}
    

  • 0
    N

    I think we can use presum and treemap.
    When we compute the presum for the input array, the presum will be represented by array B.
    Then we begin to iterator the array B,
    for(int k:B),
    the target we are looking for is t - k, then we will check the ceil or the floor value for t - k in the treemap. With the information, we know what's the close value of the sum of a sub array ending with a index i
    we put the presume to the treemap.
    we continue to iterator B, when we finished the iterator, we compute all the possible,
    and keep the closest one.
    Now we get the solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.