Minimum Subarray sum with atleast one repeated value.
Given an integer array arr[], the task is to find a minimum subarray sum that has at least one repeated value. If no such subarray is present print -1.
Examples:
Input: arr[] = {1, 3, 2, 1, 8, 2}
Output: 7
Explanation: There were 2 possible subarray’s {1, 3, 2, 1} with sum = 7 and {2, 1, 8, 2} with sum = 13, so the answer is 7Input: arr[] = {5, 3, 2, 4, 7}
Output: -1
Explanation: As all the numbers are unique No such subarray is present, so the answer is -1.
Approach: To solve the problem follow the below idea:
Approach is pretty simple we pre-compute the prefix sum array and then we iterate over the array arr[] and check the last occurence index of the current element (if present) and with the help of prefix sum array calculate the sum of the that subarray part then update minimum answer accordingly,also we need to update the last occurance index of the current element.
Steps to code the above approach:
- Initialize an array to compute the prefix sum array
- Declare an unordered map of int, int to store the last occurrence of integers present in the array
- Compute the prefix sum array
- Iterate through the original array and search in the unordered map for the last occurrence of the current value(if present )
- Calculate the sum of the subarray sum using prefix sum array by the current index value in prefix sum – the last occurrence value in prefix sum + current value and calculate the minimum answer by comparing.
Implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int minSum(vector< int > vec) { // size of the vector int n = vec.size(); // initializing the answer long ans = LONG_MAX; // prefix sum array vector< long > prefixSum(vec.size()); // pre computing prefix sum for ( int i = 0; i < vec.size(); i++) { if (i == 0) { prefixSum[i] = vec[i]; } else { // curr_sum = summ_till_prev + curr_element prefixSum[i] = prefixSum[i - 1] + vec[i]; } } // u_map to store latest index of every number unordered_map< int , int > umap; for ( int i = 0; i < vec.size(); i++) { // Checking prev occurence if (umap.find(vec[i]) != umap.end()) { // If found then val stores the // index of prev_occurence of // the curr_element long val = umap[vec[i]]; // Sum of the subtract from val // index to current index long cc = prefixSum[i] - prefixSum[val] + vec[val]; // Comparing with the previously // stored answer and updating // if needed ans = min(ans, cc); } // Updating the latest index of // the current element umap[vec[i]] = i; } // If no such subarray returing -1 if (ans == LONG_MAX) return -1; // Return answer return ans; } // Function Call int main() { vector< int > arr = { 1, 3, 2, 1, 8, 2 }; // Function Call cout << minSum(arr); return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { public static int minSum( int [] arr) { // Size of the array int n = arr.length; // Initializing the answer long ans = Long.MAX_VALUE; // Prefix sum array long [] prefixSum = new long [arr.length]; // Precomputing prefix sum for ( int i = 0 ; i < arr.length; i++) { if (i == 0 ) { prefixSum[i] = arr[i]; } else { // curr_sum = sum_till_prev + curr_element prefixSum[i] = prefixSum[i - 1 ] + arr[i]; } } // Map to store the latest index of every number Map<Integer, Integer> map = new HashMap<>(); for ( int i = 0 ; i < arr.length; i++) { // Checking previous occurrence if (map.containsKey(arr[i])) { // If found, then val stores the index of the previous // occurrence of the current element int val = map.get(arr[i]); // Sum of the subarray from val index to the current index long cc = prefixSum[i] - prefixSum[val] + arr[val]; // Comparing with the previously stored answer and updating if needed ans = Math.min(ans, cc); } // Updating the latest index of the current element map.put(arr[i], i); } // If no such subarray exists, return -1 if (ans == Long.MAX_VALUE) return - 1 ; // Return the answer return ( int ) ans; } // Function Call public static void main(String[] args) { int [] arr = { 1 , 3 , 2 , 1 , 8 , 2 }; // Function Call System.out.println(minSum(arr)); } } // This code is contributed by rambabuguphka |
Python3
def GFG(arr): # Size of the array n = len (arr) # Initializing the answer ans = float ( 'inf' ) # Prefix sum array prefixSum = [ 0 ] * n # Precomputing prefix sum for i in range (n): if i = = 0 : prefixSum[i] = arr[i] else : # curr_sum = sum_till_prev + curr_element prefixSum[i] = prefixSum[i - 1 ] + arr[i] # Dictionary to store the latest index of every number dictionary = {} for i in range (n): # Checking previous occurrence if arr[i] in dictionary: # If found, then val stores the index of # the previous occurrence of the current element val = dictionary[arr[i]] # Sum of the subarray from val index to # the current index cc = prefixSum[i] - prefixSum[val] + arr[val] # Comparing with the previously stored answer and # updating if needed ans = min (ans, cc) # Updating the latest index of current element dictionary[arr[i]] = i # If no such subarray exists # return -1 if ans = = float ( 'inf' ): return - 1 # Return the answer return ans # Function Call arr = [ 1 , 3 , 2 , 1 , 8 , 2 ] print (GFG(arr)) |
C#
using System; using System.Collections.Generic; public class GFG { public static int MinSum( int [] arr) { // Size of the array int n = arr.Length; // Initializing the answer long ans = long .MaxValue; // Prefix sum array long [] prefixSum = new long [arr.Length]; // Precomputing prefix sum for ( int i = 0; i < arr.Length; i++) { if (i == 0) { prefixSum[i] = arr[i]; } else { // curr_sum = sum_till_prev + curr_element prefixSum[i] = prefixSum[i - 1] + arr[i]; } } // Dictionary to store the latest index of every // number Dictionary< int , int > map = new Dictionary< int , int >(); for ( int i = 0; i < arr.Length; i++) { // Checking previous occurrence if (map.ContainsKey(arr[i])) { // If found, then val stores the index of // the previous occurrence of the current // element int val = map[arr[i]]; // Sum of the subarray from val index to the // current index long cc = prefixSum[i] - prefixSum[val] + arr[val]; // Comparing with the previously stored // answer and updating if needed ans = Math.Min(ans, cc); } // Updating the latest index of the current // element map[arr[i]] = i; } // If no such subarray exists, return -1 if (ans == long .MaxValue) return -1; // Return the answer return ( int )ans; } // Function Call public static void Main( string [] args) { int [] arr = { 1, 3, 2, 1, 8, 2 }; // Function Call Console.WriteLine(MinSum(arr)); } } |
Javascript
function GFG(arr) { // Size of the array const n = arr.length; // Initializing the answer let ans = Number.MAX_SAFE_INTEGER; // Prefix sum array const prefixSum = new Array(n); // Precomputing prefix sum for (let i = 0; i < n; i++) { if (i === 0) { prefixSum[i] = arr[i]; } else { // curr_sum = sum_till_prev + curr_element prefixSum[i] = prefixSum[i - 1] + arr[i]; } } // Map to store the latest index of every number const map = new Map(); for (let i = 0; i < n; i++) { // Checking previous occurrence if (map.has(arr[i])) { // If found, then val stores the index of // the previous occurrence of the current element const val = map.get(arr[i]); // Sum of the subarray from val index to // the current index const cc = prefixSum[i] - prefixSum[val] + arr[val]; // Comparing with the previously stored answer and // updating if needed ans = Math.min(ans, cc); } // Updating the latest index of current element map.set(arr[i], i); } // If no such subarray exists // return -1 if (ans === Number.MAX_SAFE_INTEGER) { return -1; } // Return the answer return ans; } // Function Call const arr = [1, 3, 2, 1, 8, 2]; console.log(GFG(arr)); |
7
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us