First subarray with negative sum from the given Array

0 0 13 minutes read

Given an array arr[] consisting of N integers, the task is to find the start and end indices of the first subarray with a Negative Sum. Print “-1” if no such subarray exists. Note: In the case of multiple negative-sum subarrays in the given array, the first subarray refers to the subarray with the lowest starting index.

Examples:

Input: arr[] = {3, 3, -4, -2} Output: 1 2 Explanation: The first subarray with negative sum is from index 1 to 2 that is arr[1] + arr[2] = -1. Input: arr[] = {1, 2, 3, 10}. Output: -1 Explanation: No Subarray with negative sum exists.

Naive Approach: The naive approach is to generate all subarrays from left to right in the array and check whether any of these subarrays have a negative sum or not. If yes then print the starting and ending index of that subarray.

Steps to implement-

Declare a vector “ans” to store the answer
Run two loops to find all subarrays
Simultaneously find the sum of all elements of the subarray
If the sum of all elements of the subarray became negative then push starting and last index of the subarray into the vector and return/print that
In the last, if nothing got printed or returned then return or print “-1”

Code-

C++

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the index
// of first negative subarray sum
vector<int> findSubarray(int arr[], int N)
{
    //To store answer
    vector<int> ans;
     
    //Find all subarray
    for(int i=0;i<N;i++){
        //To store sum of subarray
        int sum=0;
        for(int j=i;j<N;j++){
            //Take this element in finding sum of subarray
            sum+=arr[j];
             
            //If subarray has negative sum then store
            //its starting and last index in the ans vector
            if(sum<0){
                ans.push_back(i);
                ans.push_back(j);
                return ans;
            }
             
        }
    }
     
        //If any subarray sum is not negative
        ans.push_back(-1);
        return ans;
     
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, -1, 3, -4, 3, -5 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    vector<int> res = findSubarray(arr, n);
 
    // If subarray does not exist
    if (res[0] == -1)
        cout << "-1" << endl;
 
    // If the subarray exists
    else {
        cout << res[0]
             << " " << res[1];
    }
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    // Function to return the index of the first negative subarray sum
    static List<Integer> findSubarray(int[] arr, int N) {
        // To store the answer
        List<Integer> ans = new ArrayList<>();
 
        // Find all subarrays
        for (int i = 0; i < N; i++) {
            // To store the sum of subarray
            int sum = 0;
            for (int j = i; j < N; j++) {
                // Take this element in finding the sum of subarray
                sum += arr[j];
 
                // If the subarray has a negative sum, then store
                // its starting and last index in the ans list
                if (sum < 0) {
                    ans.add(i);
                    ans.add(j);
                    return ans;
                }
            }
        }
 
        // If no subarray sum is negative
        ans.add(-1);
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args) {
        // Given array arr[]
        int arr[] = { 1, 2, -1, 3, -4, 3, -5 };
 
        int n = arr.length;
 
        // Function Call
        List<Integer> res = findSubarray(arr, n);
 
        // If subarray does not exist
        if (res.get(0) == -1)
            System.out.println("-1");
 
        // If the subarray exists
        else {
            System.out.println(res.get(0) + " " + res.get(1));
        }
    }
}

Python3

def find_subarray(arr):
    # To store answer
    ans = []
    N = len(arr)
     
    # Find all subarrays
    for i in range(N):
        # To store sum of subarray
        subarray_sum = 0
        for j in range(i, N):
            # Take this element in finding sum of subarray
            subarray_sum += arr[j]
             
            # If subarray has negative sum, then store its starting and last index in the ans list
            if subarray_sum < 0:
                ans.append(i)
                ans.append(j)
                return ans
             
    # If any subarray sum is not negative
    ans.append(-1)
    return ans
 
# Driver Code
if __name__ == "__main__":
    # Given array arr[]
    arr = [1, 2, -1, 3, -4, 3, -5]
     
    # Function Call
    res = find_subarray(arr)
     
    # If subarray does not exist
    if res[0] == -1:
        print("-1")
    # If the subarray exists
    else:
        print(res[0], res[1])

Output-

0 6

Time Complexity: O(N²), because of two nested loops to find all subarray

Auxiliary Space: O(1), because no extra space has been used

Efficient Approach: The idea is to solve the problem using Prefix Sum and Hashing. Below are the steps:

Calculate the Prefix Sum of the array and store it in HashMap.
Iterate through the array and for every i^th index, where i ranges from [0, N – 1], check if the element at the i^th index is negative or not. If so, then arr[i] is the required subarray.
Otherwise, find an index starting from i + 1, where the prefix sum is smaller than the prefix sum up to i.
If any such index is found in the above step, then the subarray from indices {i, index} gives the first negative subarray.
If no such subarray is found, print “-1”. Otherwise, print the obtained subarray.

Below is the implementation of the above approach:

C++

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a sum less
// than pre_sum is present
int b_search(int pre_sum,
             map<int, vector<int> >& m,
             int index)
{
    // Returns an iterator either equal
    // to given key or next greater
    auto it = m.lower_bound(pre_sum);
 
    if (it == m.begin())
        return -1;
 
    // Decrement the iterator
    it--;
 
    // Check if the sum found at
    // a greater index
    auto it1
        = lower_bound(it->second.begin(),
                      it->second.end(),
                      index);
 
    if (*it1 > index)
        return *it1;
 
    return -1;
}
 
// Function to return the index
// of first negative subarray sum
vector<int> findSubarray(int arr[], int n)
{
    // Stores the prefix sum- index
    // mappings
    map<int, vector<int> > m;
 
    int sum = 0;
 
    // Stores the prefix sum of
    // the original array
    int prefix_sum[n];
 
    for (int i = 0; i < n; i++) {
        sum += arr[i];
 
        // Check if we get sum negative
        // starting from first element
        if (sum < 0)
            return { 0, i };
 
        prefix_sum[i] = sum;
        m[sum].push_back(i);
    }
 
    // Iterate through array find
    // the sum which is just less
    // then the previous prefix sum
    for (int i = 1; i < n; i++) {
 
        // Check if the starting element
        // is itself negative
        if (arr[i] < 0)
 
            // arr[i] becomes the required
            // subarray
            return { i, i };
 
        else {
            int pre_sum = prefix_sum[i - 1];
 
            // Find the index which forms
            // negative sum subarray
            // from i-th index
            int index = b_search(pre_sum,
                                 m, i);
 
            // If a subarray is found
            // starting from i-th index
            if (index != -1)
                return { i, index };
        }
    }
 
    // Return -1 if no such
    // subarray is present
    return { -1 };
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, -1, 3, -4, 3, -5 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    vector<int> res = findSubarray(arr, n);
 
    // If subarray does not exist
    if (res[0] == -1)
        cout << "-1" << endl;
 
    // If the subarray exists
    else {
        cout << res[0]
             << " " << res[1];
    }
    return 0;
}

Java

/*package whatever //do not write package name here */
// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // lower bound for a map's key
    public static int
    lowerBound(Map<Integer, List<Integer> > m, int pre_sum)
    {
        int ans = -1;
        for (Integer key : m.keySet()) {
            if (key >= pre_sum) {
                ans = key;
                break;
            }
        }
        return ans;
    }
 
    // lower bound for a list
    public static int lowerBoundList(List<Integer> li,
                                     int target)
    {
        int ans = -1;
        for (int i = 0; i < li.size(); i++) {
            if (li.get(i) >= target) {
                ans = i;
                break;
            }
        }
        return ans;
    }
 
    // Function to check if a sum less
    // than pre_sum is present
    public static int
    b_search(int pre_sum, Map<Integer, List<Integer> > m,
             int index)
    {
       
        // Returns an iterator either equal
        // to given key or next greater
        int it = lowerBound(m, pre_sum);
 
        if (it == 0)
            return -1;
 
        // Decrement the iterator
        it--;
 
        List<Integer> map_list = new ArrayList<Integer>();
        map_list = m.get(it);
       
        // Check if the sum found at
        // a greater index
        int it1 = lowerBoundList(map_list, index);
 
        if (map_list.get(it1) > index)
            return map_list.get(it1);
 
        return -1;
    }
 
    // Function to return the index
    // of first negative subarray sum
    public static List<Integer> findSubarray(int[] arr,
                                             int n)
    {
       
        // Stores the prefix sum- index
        // mappings
        Map<Integer, List<Integer> > m
            = new HashMap<Integer, List<Integer> >();
 
        for (int i = 0; i < n; i++) {
            List<Integer> a = new ArrayList<Integer>();
            a.add(0);
            m.put(i, a);
        }
 
        int sum = 0;
 
        // Stores the prefix sum of
        // the original array
        int[] prefix_sum = new int[n];
 
        for (int i = 0; i < n; i++) {
            sum += arr[i];
 
            // Check if we get sum negative
            // starting from first element
            if (sum < 0) {
 
                List<Integer> xyz
                    = new ArrayList<Integer>();
                xyz.add(0);
                xyz.add(i);
                return xyz;
                // return { 0, i };
            }
            List<Integer> xyz = new ArrayList<Integer>();
            xyz.add(i);
            prefix_sum[i] = sum;
            m.put(sum, xyz);
        }
 
        // Iterate through array find
        // the sum which is just less
        // then the previous prefix sum
        for (int i = 1; i < n; i++)
        {
 
            // Check if the starting element
            // is itself negative
            if (arr[i] < 0)
            {
               
                // arr[i] becomes the required
                // subarray
                List<Integer> ret
                    = new ArrayList<Integer>();
                ret.add(i);
                ret.add(i);
                return ret;
                // return { i, i };
            }
            else {
                int pre_sum = prefix_sum[i - 1];
 
                // Find the index which forms
                // negative sum subarray
                // from i-th index
                int index = b_search(pre_sum, m, i);
 
                // If a subarray is found
                // starting from i-th index
                if (index != -1) {
 
                    List<Integer> ret
                        = new ArrayList<Integer>();
                    ret.add(i);
                    ret.add(index);
                    return ret;
                    // return { i, index };
                }
            }
        }
 
        // Return -1 if no such
        // subarray is present
        List<Integer> re = new ArrayList<Integer>();
        re.add(-1);
        return re;
    }
 
    public static void main(String[] args)
    {
       
        // Given array arr[]
        int[] arr = { 1, 2, -1, 3, -4, 3, -5 };
 
        int n = arr.length;
 
        // Function Call
        List<Integer> res = new ArrayList<Integer>();
        res = findSubarray(arr, n);
 
        // If subarray does not exist
        if (res.get(0) == -1)
            System.out.println("-1");
 
        // If the subarray exists
        else {
            System.out.print(res.get(0));
            System.out.print(" ");
            System.out.println(res.get(1));
        }
    }
}
 
// This code is contributed by akashish__

Python3

# lower bound for a dictionary's key     
def lowerBound(m, pre_sum):
  ans = -1
  for key in m:
    if (key >= pre_sum):
      ans = key
      break
  return ans
 
# lower bound for a list
def lowerBoundList(li, target):
  ans = -1
  for i in range(0,len(li)):
    if (li[i] >= target):
      ans = i
      break
  return ans
 
# Function to check if a sum less
# than pre_sum is present
def b_search(pre_sum, m, index):
   
  # Returns an iterator either equal
  # to given key or next greater
  it = lowerBound(m, pre_sum)
  if (it == 0):
    return -1
 
  # Decrement the iterator
  it = it - 1
 
  map_list = m[it]
  # Check if the sum found at
  # a greater index
  it1 = lowerBoundList(map_list, index)
 
  if (map_list[it1] > index): 
    return map_list[it1]
 
  return -1
 
# Function to return the index
# of first negative subarray sum
def findSubarray(arr, n):
   
  # Stores the prefix sum- index
  # mappings
  m = {}
   
  for i in range(0,n): 
    a = [0]
    m[i] = a
 
  sum = 0
 
  # Stores the prefix sum of
  # the original array
  prefix_sum = [0]*n
   
  for i in range(0,n):
    sum += arr[i]
 
    # Check if we get sum negative
    # starting from first element
    if (sum < 0):
      xyz = [0,i]
      return xyz
 
    xyz = [i]
    prefix_sum[i] = sum
    m[sum] = xyz
 
  # Iterate through array find
  # the sum which is just less
  # then the previous prefix sum
  for i in range(1,n):
       
    # Check if the starting element
    # is itself negative
    if (arr[i] < 0):
         
      # arr[i] becomes the required
      # subarray
      ret = [i,i]
      return ret
    else:
         
      pre_sum = prefix_sum[i - 1]
 
      # Find the index which forms
      # negative sum subarray
      # from i-th index
      index = b_search(pre_sum, m, i)
 
      # If a subarray is found
      # starting from i-th index
      if (index != -1):
        ret = [i,index]
        return ret
 
  # Return -1 if no such
  # subarray is present
  re = [-1]
  return re
   
# Given array arr[]
arr = [ 1, 2, -1, 3, -4, 3, -5 ]
 
n = len(arr)
 
# Function Call
res = findSubarray(arr, n)
 
# If subarray does not exist
if (res[0] == -1):
  print("-1")
# If the subarray exists
else:
  print(res)
 
# This code is contributed by akashish__

C#

using System;
using System.Collections.Generic;
 
public class GFG
{
     
  // lower bound for a dictionary's key     
    public static int
    lowerBound(Dictionary<int, List<int> > m, int pre_sum)
    {
        int ans = -1;
        foreach(KeyValuePair<int, List<int> > kvp in m)
        {
            if (kvp.Key >= pre_sum) {
                ans = kvp.Key;
                break;
            }
        }
        return ans;
    }
 
      // lower bound for a list
    public static int lowerBoundList(List<int> li,
                                     int target)
    {
        int ans = -1;
        for (int i = 0; i < li.Count; i++) {
            if (li[i] >= target) {
                ans = i;
                break;
            }
        }
        return ans;
    }
 
    // Function to check if a sum less
    // than pre_sum is present
    public static int
    b_search(int pre_sum, Dictionary<int, List<int> > m,
             int index)
    {
        // Returns an iterator either equal
        // to given key or next greater
        int it = lowerBound(m, pre_sum);
 
        if (it == 0)
            return -1;
 
        // Decrement the iterator
        it--;
 
        List<int> map_list = new List<int>();
        map_list = m[it];
        // Check if the sum found at
        // a greater index
        int it1 = lowerBoundList(map_list, index);
 
        if (map_list[it1] > index)
            return map_list[it1];
 
        return -1;
    }
 
    // Function to return the index
    // of first negative subarray sum
    public static List<int> findSubarray(int[] arr, int n)
    {
        // Stores the prefix sum- index
        // mappings
        Dictionary<int, List<int> > m
            = new Dictionary<int, List<int> >();
       
      for(int i=0;i<n;i++)
      {
        List<int> a = new List<int>();
        a.Add(0);
          m.Add(i,a);
      }
 
        int sum = 0;
 
        // Stores the prefix sum of
        // the original array
        int[] prefix_sum = new int[n];
 
        for (int i = 0; i < n; i++) {
            sum += arr[i];
 
            // Check if we get sum negative
            // starting from first element
            if (sum < 0) {
 
                List<int> xyz = new List<int>();
                xyz.Add(0);
                xyz.Add(i);
                return xyz;
                // return { 0, i };
            }
 
            prefix_sum[i] = sum;
            m[sum].Add(i);
        }
 
        // Iterate through array find
        // the sum which is just less
        // then the previous prefix sum
        for (int i = 1; i < n; i++) {
 
            // Check if the starting element
            // is itself negative
            if (arr[i] < 0) {
                // arr[i] becomes the required
                // subarray
                List<int> ret = new List<int>();
                ret.Add(i);
                ret.Add(i);
                return ret;
              // return { i, i };
            }
            else {
                int pre_sum = prefix_sum[i - 1];
 
                // Find the index which forms
                // negative sum subarray
                // from i-th index
                int index = b_search(pre_sum, m, i);
 
                // If a subarray is found
                // starting from i-th index
                if (index != -1) {
 
                    List<int> ret = new List<int>();
                    ret.Add(i);
                    ret.Add(index);
                    return ret;
                    // return { i, index };
                }
            }
        }
 
        // Return -1 if no such
        // subarray is present
        List<int> re = new List<int>();
        re.Add(-1);
        return re;
    }
 
    static public void Main()
    {
        // Given array arr[]
        int[] arr = { 1, 2, -1, 3, -4, 3, -5 };
 
        int n = arr.Length;
 
        // Function Call
        List<int> res = new List<int>();
        res = findSubarray(arr, n);
 
        // If subarray does not exist
        if (res[0] == -1)
            Console.WriteLine("-1");
 
        // If the subarray exists
        else {
            Console.WriteLine(res[0] + " " + res[1]);
        }
    }
}
 
// This code is contributed by akashish__

Javascript

<script>
 
// lower bound for a dictionary's key     
function lowerBound(m, pre_sum)
{
    let ans = -1;
    for (const [key, value] of Object.entries(m)) {
        if (key >= pre_sum) {
            ans = key;
            break;
        }
         
    }
    return ans;
}
 
  // lower bound for a list
function lowerBoundList(li, target)
{
    let ans = -1;
    for (let i = 0; i < li.Count; i++) {
        if (li[i] >= target) {
            ans = i;
            break;
        }
    }
    return ans;
}
 
// Function to check if a sum less
// than pre_sum is present
function b_search(pre_sum, m, index)
{
    // Returns an iterator either equal
    // to given key or next greater
    let it = lowerBound(m, pre_sum);
 
    if (it == 0)
        return -1;
 
    // Decrement the iterator
    it--;
 
    map_list = [];
    map_list = m[it];
    // Check if the sum found at
    // a greater index
    let it1 = lowerBoundList(map_list, index);
 
    if (map_list[it1] > index)
        return map_list[it1];
 
    return -1;
}
 
// Function to return the index
// of first negative subarray sum
function findSubarray(/*int[]*/ arr, n)
{
    // Stores the prefix sum- index
    // mappings
    m = {};
   
  for(let i=0;i<n;i++)
  {
    a = [0];
    m[i]=a;
  }
 
    let sum = 0;
 
    // Stores the prefix sum of
    // the original array
    let prefix_sum = new Array(n);
 
    for (let i = 0; i < n; i++) {
        sum += arr[i];
 
        // Check if we get sum negative
        // starting from first element
        if (sum < 0) {
            xyz = [0,i];
            return xyz;
        }
 
        prefix_sum[i] = sum;
        m[sum] = i;
    }
 
    // Iterate through array find
    // the sum which is just less
    // then the previous prefix sum
    for (let i = 1; i < n; i++) {
 
        // Check if the starting element
        // is itself negative
        if (arr[i] < 0) {
            // arr[i] becomes the required
            // subarray
            ret = [i,i];
            return ret;
        }
        else {
            let pre_sum = prefix_sum[i - 1];
 
            // Find the index which forms
            // negative sum subarray
            // from i-th index
            let index = b_search(pre_sum, m, i);
 
            // If a subarray is found
            // starting from i-th index
            if (index != -1) {
                ret = [i,index];
                return ret;
            }
        }
    }
 
    // Return -1 if no such
    // subarray is present
    re = [-1];
    return re;
}
// Given array arr[]
let arr = [ 1, 2, -1, 3, -4, 3, -5 ];
 
let n = arr.length;
 
// Function Call
let res = findSubarray(arr, n);
 
// If subarray does not exist
if (res[0] == -1)
    console.log("-1");
 
// If the subarray exists
else {
    console.log(res);
}
 
// This code is contributed by akashish__
 
</script>

Output

0 6

Time Complexity: O(N * log N) Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!