Optimize FOR loop for adding array elements to set

Question

I have an array Ar of size N(Ar[N]). I have to divide the Ar[N] into sub arrays of size K and then add them to a Set S. For example if Ar[5] = {1,2,3,4,5} and K = 3 then, Sub arrays will be {1,2,3},{2,3,4},{3,4,5} Now I have to add these sub arrays to the Set and continue my computations.

Here is my code :

int max = 0;
for(int j=0;j<=N-k;j++){
            Set<Integer> set = new HashSet<>();
            for(int l=j;l<j+K;l++){
                set.add(Ar[l]);
            }
if(set.size >= max) max = set.size;
        }
System.out.println(max);

Is there any way that I can get rid of the nested for loop as in worst case N can be 1000000.
NOTE : The set should only contain unique values. Hope I am clear.

There isn't really a way to make this more efficient given the problem as you've stated it. Anything you do is going to need to end up doing O(NK) work. — Louis Wasserman, Aug 09 '20 at 05:04
Can you give the full problem statement - cause at this level I agree with Louis — Deian, Aug 09 '20 at 05:11
Can you show how you *use* the set of sub arrays? Perhaps it's possible to change the program so it's not necessary to construct this set entirely — Joni, Aug 09 '20 at 05:11
Hi @Joni, I calculate the max size of the set. I added it to my code. please have a look. — Subham, Aug 09 '20 at 05:36
But in our code I see a set of Integer not a set of array of Integer. What did I miss? — Alexandr Ivanov, Aug 09 '20 at 06:20
Subham - You seem to be confused. The way you have explained your question, [the answer by saka1029](https://stackoverflow.com/a/63322720/10819573) which he has deleted and therefore is visible to only ones who have 10k+ reputation points, was correct. And as @Joni has mentioned, it's not necessary to construct this set entirely. If all you want is the total number of elements in all the sub-arrays, it will be `(N - K + 1) * K`. — Arvind Kumar Avinash, Aug 09 '20 at 07:50

Eklavya · Accepted Answer · 2020-08-09T07:58:02.050

Maintain a window of i-k-1 to i of set when traversing the array. You can use HashMap to count the frequency of value and remove it when the frequency is zero. And update max value of set then you will get max set size of each subarray's set.

int[] arr = {1,2,1,4,1};
int k = 3;
int max = 0;
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
  set.add(arr[i]);
  map.merge(arr[i], 1, Integer::sum);
  if(i >= k) {
    map.merge(arr[i-k], -1, Integer::sum);
    if(map.get(arr[i-k]) == 0) {
      set.remove(arr[i-k]);
    }
  }
  if(set.size() >= max) {
    max = set.size();
  }
}

Did you check this solution ? – Eklavya Aug 09 '20 at 19:23 — Eklavya, Aug 09 '20 at 19:23

Nowhere Man · Answer 2 · 2020-08-09T08:24:02.343

If actual task is to define the maximum size of a subset after dividing into K elements, it can be implemented this way:

public static long findMaxSize(int[] arr, int k) {
    return IntStream.rangeClosed(0, arr.length - k)
                    .mapToLong(i -> 
                        Arrays.stream(Arrays.copyOfRange(arr, i, i + k))
                              .distinct().count())
                    .max().getAsLong();
}

Also, splitting of the input array by K elements into subsets may be implemented this way:

public static Set<Set<Integer>> splitIntoSubsetsByK(int[] arr, int k) {
    return IntStream.rangeClosed(0, arr.length - k)
                    .mapToObj(i -> Arrays.stream(Arrays.copyOfRange(arr, i, i + k))
                        .boxed().collect(Collectors.toSet()))
                    .collect(Collectors.toCollection(LinkedHashSet::new));
    }

Test and output:

int[] arr = {1, 2, 2, 2, 1};
int k = 3;

Set<Set<Integer>> result = splitIntoSubsetsByK(arr, k);
result.forEach(System.out::println);

System.out.println(findMaxSize(arr, k));

[1, 2]
[2]
2

score 0 · Answer 3 · answered Aug 09 '20 at 07:57

Alternative solution. Try to use "subList()" described in: How to use subList()

See example below:

public static void main(String[] args) {
    int startNumber = 1;
    int endNumber = 5;
    List<Integer> mainList = new ArrayList<>();
    for (int i = startNumber; i <= endNumber; i++) {
        mainList.add(i);
    }

    // See mainList:
    System.out.println(mainList); // output: [1, 2, 3, 4, 5]

    int sizeOfEachSubList = 3;
    int loopStopPoint = mainList.size() - sizeOfEachSubList;
    List<List<Integer>> listOfLists = new ArrayList<>();
    for (int i = 0; i <= loopStopPoint; i++) {
        List<Integer> subList = mainList.subList(i, sizeOfEachSubList + i);
        listOfLists.add(subList);
    }

    //See all lists:
    System.out.println(listOfLists); // output: [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
}

Optimize FOR loop for adding array elements to set

3 Answers3