Reduce time complexity to process sub-arrays

Question

For a given integer array of size n, find all possible sub arrays of size k which range from 1 to n.

Now find the common item which is also a minimum in all sub-arrays of size k, if no common item is found then use -1 and add that to the result list.

For example:

Input array : [4,3,3,4,2]

Result :

[-1,-1,3,3,2]

Explanation:

k = 1, [4],[3],[3],[4],[2], there is no common item so -1
k = 2, [4,3],[3,3],[3,4],[4,2], there is no common item so -1
k = 3, [4,3,3], [3,3,4], [3,4,2], common item is 3
k = 4, [4,3,3,4],[3,3,4,2], common items are 3 and 4, the minimum is 3
k = 5, [4,3,3,4,2], minimum common item is 2

This is my naive approach code along with comments:

public static List<Integer> solve(int[] ar) {
 // Get all subarrays in a map, with key as sub-arrays size from 1 to n and value as the corresponding sub-arrays 
 Map<Integer, List<List<Integer>>> map = subArrays(ar);
 int n = map.size();
 List<Integer> result = new ArrayList<>();
 for(int i=0; i<n; i++) {
 List<List<Integer>> list = map.get(i+1);
 // Get the common minimum item and store in result.
 result.add(solve(list));
 }
 return result;
}
// Logic to check for a given subarray of size k, get the minimum common item
public static int solve(List<List<Integer>> list) {
 int n = list.get(0).size();
 int min = Integer.MAX_VALUE;
 boolean found = false;
 for (int i = 0; i < n; i++) {
 int num = list.get(0).get(i);
 boolean isCommon = true;
 
 for(int j=1; j<list.size(); j++) {
 List<Integer> arr = list.get(j);
 if (!contains(arr, num)) {
 isCommon = false;
 break;
 }
 }
 if (isCommon) {
 min = Math.min(min, num);
 found = true;
 }
 }
 return found ? min : -1; // Return -1 if there is no common element.
}
// Logic to check if the number is present in given arr
public static boolean contains(List<Integer> arr, int num) {
 for (int value : arr) {
 if (value == num) {
 return true;
 }
 }
 return false;
}
// Logic to find all possible sub arrays of size 1 to n and stored in map
public static Map<Integer, List<List<Integer>>> subArrays(int[] arr) {
 int n = arr.length;
 Map<Integer, List<List<Integer>>> map = new HashMap<>();
 for(int i=0; i<n; i++) {
 map.put(i+1, new ArrayList<>());
 }
 for (int i = 0; i < n; i++) {
 for (int j = i; j < n; j++) {
 int size = j - i+1;
 List<Integer> e = new ArrayList<>();
 for (int k = i; k <= j; k++) {
 e.add(arr[k]);
 }
 map.get(size).add(e);
 }
 }
 return map;
}

}

Here I am using a nested loop so time complexity is O(n^3), also using a map to store all possible sub-arrays that increase space complexity.

How to solve this in less time and less space.

Update:

I further tried to reduce time complexity using below code:

public static List<Integer> solve(int[] ar) {
 int n = map.size();
 List<Integer> result = new ArrayList<>();
 for(int i=0; i<n; i++) {
 result.add(minCommonElementInSubarrays(ar, i+1));
 }
 return result;
}
static void minCommonElementInSubarrays(int arr[], int K) { 
 int N = arr.length;
 int c; 
 
 // If N is odd then update 
 // C as K >= (N + 1)/2 
 if ((N + 1) % 2 == 0) 
 { 
 c = (N + 1) / 2; 
 } 
 
 // If N is even then update 
 // C as K >= (N + 1)/2 + 1 
 else
 { 
 c = (N + 1) / 2 + 1; 
 } 
 
 // If K < C, return "=1" 
 if (K < c)
 { 
 return -1;
 } 
 
 // Otherwise 
 else
 { 
 
 // Initialize result variable 
 int ar = Integer.MAX_VALUE; 
 
 // Find minimum element 
 for(int i = N - K; i < K; i++)
 { 
 ar = Math.min(arr[i], ar); 
 } 
 
 // return the minimum value 
 return ar;
 } 
}

But still this code runs in O(n^2) time complexity, I want to reduce it further.

• greybeard: The improvement doesn't even compile. What in the 2nd solve(int[] ar) is map? I read the problem statement to require common values; the improvement is about elements included in all sub-arrays of a specified size: try 2, 1, 2, 1, 2.

Answer 1

As already explained by previous answer and comments the choice of solving the problem using just the List structure is questionable, for example taking your [4,3,3,4,2] input array and the value k = 3:

k = 3, [4,3,3], [3,3,4], [3,4,2], common item is 3

Every subarray can be obtained from the previous one in the chain deleting the first one element and adding the next one outside the window of length k or equivalently move the window of 1 element at every iteration:

input = [4, 3, 3, 4, 2] k = 3
first iteration: [4, 3, 3, 4, 2] = [4, 3, 3]
 [---k---]
second iteration: [4, 3, 3, 4, 2] = [3, 3, 4]
 [---k---]
third iteration: [4, 3, 3, 4, 2] = [3, 4, 2]
 [---k---]

To find the mininum common element between these subarrays you can erase the duplicates and then compares the Set sets obtained from these subarrays:

input = [4, 3, 3, 4, 2] k = 3
first iteration: [4, 3, 3, 4, 2] = [4, 3, 3] = {4, 3}
 [---k---]
second iteration: [4, 3, 3, 4, 2] = [3, 3, 4] = {3, 4}
 [---k---]
{4, 3} ∩ {3, 4} = {3, 4}
third iteration: [4, 3, 3, 4, 2] = [3, 4, 2] = {3, 4, 2}
 [---k---]
{3, 4} ∩ {3, 4, 2} = {3, 4}
Minimum is 3

You can so obtain a List<Integer> list from the first subarray of length k and its set, the next iterations will process the next subarrays and their sets doing the consecutive intersection; if one of the obtained sets after the intersection operation is empty the -1 value will be returned otherwise the minimum will be returned.

 public class Exercise {
 public static void main(String[] args) {
 int[] arr = {4, 3, 3, 4, 2};
 for (int k = 1; k <= arr.length; ++k) {
 System.out.println(solve(arr, k));
 }
 
 }
 
 public static int solve(int[] arr, int k) {
 //initialization of the first subarray and its set
 List<Integer> ints = IntStream.of(Arrays.copyOf(arr, k))
 .boxed()
 .collect(Collectors.toList());
 Set<Integer> set = new TreeSet<>(ints);
 
 //consecutive subarrays and their sets with intersections
 for (int i = 1; i + k - 1 < arr.length; ++i) {
 ints.remove(0);
 ints.add(arr[i + k - 1]);
 //intersection with no need to create a set offered by jdk library
 set.retainAll(ints); 
 if (set.isEmpty()) { return -1; }
 }
 return Collections.min(set);
 }
}

I used just the built in data structures present in the jdk library, if you want to improve performance you have to build custom data structures.

• dariosicily: @greybeard You are absolutely right.

Answer 2

I think there is a easier breakdown of this problem. One detail to consider about this problem is that other than the initial array, the sub-arrays only need to be considered a type of Set instead of Lists. From there, at each step, you are unioning and intersecting Sets to figure out the minimums.

To simplify this further, you could create a simple data structure that is a Set but also tracks the minimum of that set—let's call it a MinSet. When unioning two sets A and B, the minimum of the result is just the smaller of the minimums of A and B, which can be determined in constant time (not including the union itself). The intersection is trickier but can be done while the intersection is calculated.

This way, you can reuse the minimum calculation for the next k.

• greybeard: (Any comment on if ((n + 2) / 2 < K) return -1;?)
• greybeard: (I'm not sure I understand The intersection is trickier but can be done while the intersection is calculated.)