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
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

/*
   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;
}

 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)
	{
		PrefixSuffix task = new PrefixSuffix();
		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 
		*/
		task.minPrefixSuffix(arr, n);
	}
}

 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()
{
	PrefixSuffix *task = new PrefixSuffix();
	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 
	*/
	task->minPrefixSuffix(arr, n);
	return 0;
}

 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)
	{
		PrefixSuffix task = new PrefixSuffix();
		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 
		*/
		task.minPrefixSuffix(arr, n);
	}
}

 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)
}

 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()
{
	$task = new PrefixSuffix();
	$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 
	*/
	$task->minPrefixSuffix($arr, $n);
}
main();

 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 task = new PrefixSuffix();
	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 
	*/
	task.minPrefixSuffix(arr, n);
}
main();

 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() :
	task = PrefixSuffix()
	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 
	task.minPrefixSuffix(arr, n)

if __name__ == "__main__": main()

 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() 
	task = PrefixSuffix.new()
	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 
	task.minPrefixSuffix(arr, n)
end

main()

 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 
		*/
		task.minPrefixSuffix(arr, n);
	}
}

 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 task: PrefixSuffix = PrefixSuffix();
	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 
	*/
	task.minPrefixSuffix(arr, n);
}
main();

 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 task: PrefixSuffix = PrefixSuffix();
	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 
	*/
	task.minPrefixSuffix(arr, n);
}

 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.