Posted on by Kalkicode
Code Array

# Find index with minimum sum of prefix and suffix sums in an array

In this article, we will explore the problem of finding the index with the minimum sum of prefix and suffix sums in an array. We'll describe the problem statement, provide a step-by-step explanation of the algorithm to solve it, and analyze the time complexity of the code. By the end of this article, you'll have a clear understanding of how to find the index that minimizes the sum of prefix and suffix sums in an array.

## Problem Statement

Given an array of integers, we need to find an index such that the sum of the prefix elements up to that index and the sum of the suffix elements from that index onward are minimized. Formally, we want to find an index `i` that minimizes the sum `prefixSum[0..i] + suffixSum[i..n-1]`, where `n` is the size of the array.

## Solution Idea

To solve this problem efficiently, we can pre-calculate prefix sums and suffix sums for each index and then iterate through the array to find the index that minimizes the sum of prefix and suffix sums.

## Standard Pseudocode

Here's the pseudocode that outlines the approach to find the index with the minimum sum of prefix and suffix sums:

``````function minPrefixSuffix(arr):
Initialize an array prefix of size n
Initialize an array suffix of size n
Initialize a variable position to 0

Calculate prefix[0] = arr[0]
Calculate suffix[n-1] = arr[n-1]

for i from 1 to n-1:
prefix[i] = prefix[i-1] + arr[i]

for i from n-2 to 0:
suffix[i] = suffix[i+1] + arr[i]

Initialize a variable sum = prefix[0] + suffix[0]

for i from 1 to n-1:
if prefix[i] + suffix[i] < sum:
position = i
sum = prefix[i] + suffix[i]

return position``````

## Algorithm Explanation

1. We start by initializing two arrays `prefix` and `suffix`, both of size `n` where `n` is the size of the input array. These arrays will store the prefix sums and suffix sums for each index.

2. We calculate the first element of `prefix` by directly copying the first element of the input array: `prefix[0] = arr[0]`.

3. Similarly, we calculate the last element of `suffix` by copying the last element of the input array: `suffix[n-1] = arr[n-1]`.

4. We then use a loop to calculate the rest of the `prefix` array. For each index `i` from 1 to `n-1`, we calculate `prefix[i]` by adding the current element `arr[i]` to the previous prefix sum `prefix[i-1]`.

5. We use another loop to calculate the `suffix` array in reverse. For each index `i` from `n-2` to 0, we calculate `suffix[i]` by adding the current element `arr[i]` to the next suffix sum `suffix[i+1]`.

6. We initialize a variable `sum` to store the minimum sum of prefix and suffix sums. We also initialize a variable `position` to store the index that corresponds to the minimum sum.

7. We then iterate through the array using a loop from 1 to `n-1`. For each index `i`, we check if the sum of `prefix[i]` and `suffix[i]` is less than the current minimum `sum`. If it is, we update `position` with the current index `i` and update `sum` with the new minimum sum.

8. After iterating through the array, the variable `position` will hold the index that corresponds to the minimum sum of prefix and suffix sums.

9. We return the value of `position` as the result.

## Code Solution

``````/*
C program for
Find index with minimum sum of prefix and
suffix sums in an Array
*/
#include <stdio.h>

void minPrefixSuffix(int arr[], int n)
{
// This is use collect prefix sum
int prefix[n];
// This is use collect suffix sum
int suffix[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
printf(" Position : %d", position);
}
int main(int argc, char
const *argv[])
{
int arr[] = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix

arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
minPrefixSuffix(arr, n);
return 0;
}``````

#### Output

`` Position : 4``
``````/*
Java program for
Find index with minimum sum of prefix and suffix sums in an array
*/
public class PrefixSuffix
{
public void minPrefixSuffix(int[] arr, int n)
{
// This is use collect prefix sum
int[] prefix = new int[n];
// This is use collect suffix sum
int[] suffix = new int[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
System.out.print(" Position : " + position);
}
public static void main(String[] args)
{
int[] arr = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
}``````

#### Output

`` Position : 4``
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
public: void minPrefixSuffix(int arr[], int n)
{
// This is use collect prefix sum
int prefix[n];
// This is use collect suffix sum
int suffix[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
cout << " Position : " << position;
}
};
int main()
{
int arr[] = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
return 0;
}``````

#### Output

`` Position : 4``
``````// Include namespace system
using System;
/*
Csharp program for
Find index with minimum sum of prefix and
suffix sums in an Array
*/
public class PrefixSuffix
{
public void minPrefixSuffix(int[] arr, int n)
{
// This is use collect prefix sum
int[] prefix = new int[n];
// This is use collect suffix sum
int[] suffix = new int[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
Console.Write(" Position : " + position);
}
public static void Main(String[] args)
{
int[] arr = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = arr.Length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
}``````

#### Output

`` Position : 4``
``````package main
import "fmt"
/*
Go program for
Find index with minimum sum of prefix and suffix sums in an Array
*/

func minPrefixSuffix(arr[] int, n int) {
// This is use collect prefix sum
var prefix = make([] int, n)
// This is use collect suffix sum
var suffix = make([] int, n)
var position int = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
// Calculate prefix sum
for i := 1 ; i < n ; i++ {
prefix[i] = prefix[i - 1] + arr[i]
}
// Calculate suffix sum
for i := n - 2 ; i >= 0 ; i-- {
suffix[i] = suffix[i + 1] + arr[i]
}
// First pair of prefix and suffix
var sum int = prefix[0] + suffix[0]
for i := 1 ; i < n ; i++ {
if prefix[i] + suffix[i] < sum {
position = i
// We get new pair
sum = prefix[i] + suffix[i]
}
}
// Display calculated position
fmt.Print(" Position : ", position)
}
func main() {

var arr = [] int {3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 }
var n int = len(arr)
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
minPrefixSuffix(arr, n)
}``````

#### Output

`` Position : 4``
``````<?php
/*
Php program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
public	function minPrefixSuffix(\$arr, \$n)
{
// This is use collect prefix sum
\$prefix = array_fill(0, \$n, 0);
// This is use collect suffix sum
\$suffix = array_fill(0, \$n, 0);
\$position = 0;
\$prefix[0] = \$arr[0];
\$suffix[\$n - 1] = \$arr[\$n - 1];
// Calculate prefix sum
for (\$i = 1; \$i < \$n; ++\$i)
{
\$prefix[\$i] = \$prefix[\$i - 1] + \$arr[\$i];
}
// Calculate suffix sum
for (\$i = \$n - 2; \$i >= 0; --\$i)
{
\$suffix[\$i] = \$suffix[\$i + 1] + \$arr[\$i];
}
// First pair of prefix and suffix
\$sum = \$prefix[0] + \$suffix[0];
for (\$i = 1; \$i < \$n; ++\$i)
{
if (\$prefix[\$i] + \$suffix[\$i] < \$sum)
{
\$position = \$i;
// We get new pair
\$sum = \$prefix[\$i] + \$suffix[\$i];
}
}
// Display calculated position
echo(" Position : ".\$position);
}
}

function main()
{
\$arr = array(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
\$n = count(\$arr);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
main();``````

#### Output

`` Position : 4``
``````/*
Node JS program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
minPrefixSuffix(arr, n)
{
// This is use collect prefix sum
var prefix = Array(n).fill(0);
// This is use collect suffix sum
var suffix = Array(n).fill(0);
var position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (var i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (var i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
var sum = prefix[0] + suffix[0];
for (var i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
process.stdout.write(" Position : " + position);
}
}

function main()
{
var arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6];
var n = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
main();``````

#### Output

`` Position : 4``
``````#    Python 3 program for
#    Find index with minimum sum of prefix and suffix sums in an Array
class PrefixSuffix :
def minPrefixSuffix(self, arr, n) :
#  This is use collect prefix sum
prefix = [0] * (n)
#  This is use collect suffix sum
suffix = [0] * (n)
position = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
i = 1
#  Calculate prefix sum
while (i < n) :
prefix[i] = prefix[i - 1] + arr[i]
i += 1

i = n - 2
#  Calculate suffix sum
while (i >= 0) :
suffix[i] = suffix[i + 1] + arr[i]
i -= 1

#  First pair of prefix and suffix
sum = prefix[0] + suffix[0]
i = 1
while (i < n) :
if (prefix[i] + suffix[i] < sum) :
position = i
#  We get new pair
sum = prefix[i] + suffix[i]

i += 1

#  Display calculated position
print(" Position : ", position, end = "")

def main() :
arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6]
n = len(arr)
#    arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
#    -----------------------------------------------
#    position    0   1   2  3  4   5  6   7   8  9
#    Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
#    Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
#    -----------------------------------------------
#    position 4 contain minimum prefix and suffix
#    arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
#                       ↑
#                   position

if __name__ == "__main__": main()``````

#### Output

`` Position :  4``
``````#    Ruby program for
#    Find index with minimum sum of prefix and suffix sums in an Array
class PrefixSuffix
def minPrefixSuffix(arr, n)
#  This is use collect prefix sum
prefix = Array.new(n) {0}
#  This is use collect suffix sum
suffix = Array.new(n) {0}
position = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
i = 1
#  Calculate prefix sum
while (i < n)
prefix[i] = prefix[i - 1] + arr[i]
i += 1
end

i = n - 2
#  Calculate suffix sum
while (i >= 0)
suffix[i] = suffix[i + 1] + arr[i]
i -= 1
end

#  First pair of prefix and suffix
sum = prefix[0] + suffix[0]
i = 1
while (i < n)
if (prefix[i] + suffix[i] < sum)
position = i
#  We get new pair
sum = prefix[i] + suffix[i]
end

i += 1
end

#  Display calculated position
print(" Position : ", position)
end

end

def main()
arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6]
n = arr.length
#    arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
#    -----------------------------------------------
#    position    0   1   2  3  4   5  6   7   8  9
#    Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
#    Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
#    -----------------------------------------------
#    position 4 contain minimum prefix and suffix
#    arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
#                       ↑
#                   position
end

main()``````

#### Output

`` Position : 4``
``````/*
Scala program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix()
{
def minPrefixSuffix(arr: Array[Int], n: Int): Unit = {
// This is use collect prefix sum
var prefix: Array[Int] = Array.fill[Int](n)(0);
// This is use collect suffix sum
var suffix: Array[Int] = Array.fill[Int](n)(0);
var position: Int = 0;
prefix(0) = arr(0);
suffix(n - 1) = arr(n - 1);
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix(i) = prefix(i - 1) + arr(i);
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix(i) = suffix(i + 1) + arr(i);
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix(0) + suffix(0);
i = 1;
while (i < n)
{
if (prefix(i) + suffix(i) < sum)
{
position = i;
// We get new pair
sum = prefix(i) + suffix(i);
}
i += 1;
}
// Display calculated position
print(" Position : " + position);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PrefixSuffix = new PrefixSuffix();
var arr: Array[Int] = Array(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
var n: Int = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
}``````

#### Output

`` Position : 4``
``````import Foundation;
/*
Swift 4 program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
func minPrefixSuffix(_ arr: [Int], _ n: Int)
{
// This is use collect prefix sum
var prefix: [Int] = Array(repeating: 0, count: n);
// This is use collect suffix sum
var suffix: [Int] = Array(repeating: 0, count: n);
var position: Int = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix[i] = prefix[i - 1] + arr[i];
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix[i] = suffix[i + 1] + arr[i];
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix[0] + suffix[0];
i = 1;
while (i < n)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
i += 1;
}
// Display calculated position
print(" Position : ", position, terminator: "");
}
}
func main()
{
let arr: [Int] = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6];
let n: Int = arr.count;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}
main();``````

#### Output

`` Position :  4``
``````/*
Kotlin program for
Find index with minimum sum of prefix and
suffix sums in an array
*/
class PrefixSuffix
{
fun minPrefixSuffix(arr: Array < Int > , n: Int): Unit
{
// This is use collect prefix sum
var prefix: Array < Int > = Array(n)
{
0
};
// This is use collect suffix sum
var suffix: Array < Int > = Array(n)
{
0
};
var position: Int = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix[i] = prefix[i - 1] + arr[i];
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix[i] = suffix[i + 1] + arr[i];
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix[0] + suffix[0];
i = 1;
while (i < n)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
i += 1;
}
// Display calculated position
print(" Position : " + position);
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < Int > = arrayOf(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
val n: Int = arr.count();
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position    0   1   2  3  4   5  6   7   8  9
Prefix sum [3  -3  -2  4 -3  -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4   0  3   5   6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
}``````

#### Output

`` Position : 4``

## Time Complexity Analysis

The time complexity of this algorithm is O(n), where n is the size of the input array. This is because we iterate through the array three times: once to calculate the prefix sums, once to calculate the suffix sums, and once to find the index with the minimum sum. The individual calculations and comparisons are done in constant time.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post