4
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Commented Oct 15, 2023 at 12:55

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ @greybeard You are absolutely right. \$\endgroup\$ Commented Oct 16, 2023 at 11:36
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ (Any comment on if ((n + 2) / 2 < K) return -1;?) \$\endgroup\$
    – greybeard
    Commented Oct 15, 2023 at 22:07
  • 1
    \$\begingroup\$ (I'm not sure I understand The intersection is trickier but can be done while the intersection is calculated.) \$\endgroup\$
    – greybeard
    Commented Oct 15, 2023 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.