Minimum Difference Subarrays in Java
The Minimum Difference Subarrays is a problem where we are given an array of numbers and our task is to find the minimum difference between the two subarrays. The Sub- arrays will be made from the given input array. If any element from the array is a part of a sub-array then it can not be part of another sub-array. The Sub array should not be empty. The given example shows the same.
Example 1:
Input
int arr[] = {9, 1, 5, 4, 7, 2}
Output: 2
Explanation: If we create two subarrays as subArr1 = {9, 1, 5} and subArr2 = {4, 7, 2}, then we get the sum of elements of subarrays as 9 + 1 + 5 = 15, and 4 + 7 + 2 = 13, and their difference is 15 - 13 = 2. Hence, the output is 2.
Example 2:
Input
int arr[] = {3, 6, 4, 8, 4}
Output: 1
Explanation: If we create two subarrays as subArr1 = {3, 6, 4} and subArr2 = {8, 4}, then we get the sum of elements of subarrays as 3 + 6 + 4 = 13, and 8 + 4 = 12, and their difference is 13 - 12 = 1. Hence, the output is 1.
Example 3:
Input
int arr[] = {2, 5, 9, 3, 4, 6}
Output: 3
Explanation: If we create two subarrays as: subArr1 = {2, 5, 9} and subArr2 = {3, 4, 6}, then we get the sum of elements of subarrays as: 2 + 5 + 9 = 16, and 3 + 4 + 6 = 13, and their difference is 16 - 13 = 3. Hence, the output is 3.
Approach: Using Prefix Sum
In this approach, we have included the method to find the minimum difference, the calculation of the prefix sum array, the iteration through possible partition points, and the updating of the minimum difference. The main method demonstrates the usage of the findMinimumDifference method for three different input arrays and prints the results.
FileName: SubarrayDifference.java
public class SubarrayDifference {
// Method to find the minimum difference between two subarrays using prefix sum approach
public static int findMinimumDifference(int[] arr) {
int n = arr.length;
int[] prefixSum = new int[n + 1];
// Calculate prefix sum of the array
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
int minDifference = Integer.MAX_VALUE;
// Iterate through all possible partition points
for (int i = 1; i < n; i++) {
int sum1 = prefixSum[i]; // Sum of elements in the first subarray
int sum2 = prefixSum[n] - prefixSum[i]; // Sum of elements in the second subarray
int difference = Math.abs(sum1 - sum2); // Calculate the difference
// Update the minimum difference if necessary
if (difference < minDifference) {
minDifference = difference;
}
}
return minDifference;
}
public static void main(String[] args) {
// Sample input arrays
int[] arr1 = {9, 1, 5, 4, 7, 2};
int[] arr2 = {3, 6, 4, 8, 4};
int[] arr3 = {2, 5, 9, 3, 4, 6};
// Find the minimum difference for arr1
int minDifference1 = findMinimumDifference(arr1);
System.out.println("The Minimum difference for arr1: " + minDifference1);
// Find the minimum difference for arr2
int minDifference2 = findMinimumDifference(arr2);
System.out.println("The Minimum difference for arr2: " + minDifference2);
// Find the minimum difference for arr3
int minDifference3 = findMinimumDifference(arr3);
System.out.println("The Minimum difference for arr3: " + minDifference3);
}
}
Output:
The minimum difference for arr1: 2 The minimum difference for arr2: 1 The minimum difference for arr3: 3
Complexity:
The time complexity of this problem is O(n), where n is the length of the input array. The code iterates through the array twice: once to calculate the prefix sum array and another time to find the minimum difference between the subarrays. Both iterations have a linear time complexity of O(n). Therefore, the overall time complexity of the code is O(n).
The additional space used for the prefixSum array: O(n) Other variables used in the code are of constant size. The space complexity of the code is O(n) as well since it requires an additional prefix sum array of size n+1 to store the cumulative sums.
Approach: Brute Force
In this Brute Force approach, the findMinimumDifference method iterates through all possible partition points and calculates the sum of elements for each subarray using the calculateSum helper method. It then finds the minimum difference among all the calculated differences.
FileName: SubarrayDifference.java
public class SubarrayDifference {
// Method to find the minimum difference between two subarrays using brute force approach
public static int findMinimumDifference(int[] arr) {
int n = arr.length;
int minDifference = Integer.MAX_VALUE;
// Iterate through all possible partition points
for (int i = 1; i < n; i++) {
int sum1 = calculateSum(arr, 0, i - 1); // Sum of elements in the first subarray
int sum2 = calculateSum(arr, i, n - 1); // Sum of elements in the second subarray
int difference = Math.abs(sum1 - sum2); // Calculate the difference
// Update the minimum difference if necessary
if (difference < minDifference) {
minDifference = difference;
}
}
return minDifference;
}
// Helper method to calculate the sum of elements in a given range of the array
private static int calculateSum(int[] arr, int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += arr[i];
}
return sum;
}
public static void main(String[] args) {
// Sample input arrays
int[] arr1 = {9, 1, 5, 4, 7, 2};
int[] arr2 = {3, 6, 4, 8, 4};
int[] arr3 = {2, 5, 9, 3, 4, 6};
// Find the minimum difference for arr1
int minDifference1 = findMinimumDifference(arr1);
System.out.println("The Minimum difference for arr1: " + minDifference1);
// Find the minimum difference for arr2
int minDifference2 = findMinimumDifference(arr2);
System.out.println("The Minimum difference for arr2: " + minDifference2);
// Find the minimum difference for arr3
int minDifference3 = findMinimumDifference(arr3);
System.out.println("The Minimum difference for arr3: " + minDifference3);
}
}
Output:
The minimum difference for arr1: 2 The minimum difference for arr2: 1 The minimum difference for arr3: 3
Complexity:
The time complexity of the Brute Force approach in this code is O(n^2), where n is the length of the input array. In the findMinimumDifference method, the code iterates through all possible partition points using a for loop, which takes O(n) iterations. Inside the loop, the calculateSum method is called twice, which itself iterates over a range of elements in the array. This inner loop runs in O(n) time as well. Therefore, the overall time complexity is O(n) * O(n) = O(n^2).
The space complexity of the code is O(1) since it uses a constant amount of extra space. The variables used, such as minDifference, sum1, sum2, start, end, and sum, are of constant size and do not depend on the size of the input array. Additionally, the calculateSum method does not use any additional data structures that grow with the input size. Therefore, the time complexity is O(n^2) and the space complexity is O(1).
Approach: Using Constant Space
In this Constant Space approach, for finding the minimum difference the findMinimumDifference method calculates the total sum of the array in a single iteration. Then, using a single variable leftSum, it iterates through all possible partition points and calculates the right sum as totalSum - leftSum. It then finds the minimum difference among all the calculated differences.
FileName: SubarrayDifference.java
public class SubarrayDifference {
// Method to find the minimum difference between two subarrays using constant space approach
public static int findMinimumDifference(int[] arr) {
int n = arr.length;
int totalSum = 0;
// Calculate the total sum of the array
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
int minDifference = Integer.MAX_VALUE;
int leftSum = 0;
// Iterate through all possible partition points
for (int i = 0; i < n - 1; i++) {
leftSum += arr[i];
int rightSum = totalSum - leftSum;
int difference = Math.abs(leftSum - rightSum);
// Update the minimum difference if necessary
if (difference < minDifference) {
minDifference = difference;
}
}
return minDifference;
}
public static void main(String[] args) {
// Sample input arrays
int[] arr1 = {9, 1, 5, 4, 7, 2};
int[] arr2 = {3, 6, 4, 8, 4};
int[] arr3 = {2, 5, 9, 3, 4, 6};
// Find the minimum difference for arr1
int minDifference1 = findMinimumDifference(arr1);
System.out.println("The Minimum difference for arr1: " + minDifference1);
// Find the minimum difference for arr2
int minDifference2 = findMinimumDifference(arr2);
System.out.println("The Minimum difference for arr2: " + minDifference2);
// Find the minimum difference for arr3
int minDifference3 = findMinimumDifference(arr3);
System.out.println("The Minimum difference for arr3: " + minDifference3);
}
}
Output:
The minimum difference for arr1: 2 The minimum difference for arr2: 1 The minimum difference for arr3: 3
Complexity:
The time complexity of the Constant space approach for this code is O(n), where n is the length of the input array. In the findMinimumDifference method, the code iterates through the array once to calculate the total sum, which takes O(n) time. Then, it iterates through all possible partition points, which takes O(n) time as well. Therefore, the overall time complexity is O(n) + O(n) = O(n).
The space complexity of the code is O(1) since it uses a constant amount of extra space. It does not require any additional data structures that grow with the input size. The variables used, such as totalSum, minDifference, and leftSum, are of constant size and do not depend on the size of the input array. Therefore, the time complexity is O(n) and the space complexity is O(1).