1

How to generate all subarrays from an initial array?

Let's consider an array: [1,1,1,1].

I would like to generate all possible subarrays (in no particular order).

Expected result:

[1], [1], [1], [1], 
[1, 1], [1, 1], [1, 1],
[1, 1, 1], [1, 1, 1],
[1, 1, 1, 1]

My attempt:

List<List<Integer>> list = new ArrayList<>();
generateAllSubArrays(nums, list, 0, 0);

private void generateAllSubArrays(int[] nums, List<List<Integer>> list, int start, int end) {
    if (end == nums.length) {
        List<Integer> l = new ArrayList<>();
        for (int n : nums) {
            l.add(n);
        }
        list.add(l);
    } else if (start > end) {
        generateAllSubArrays(nums, list, 0, end + 1);
    } else {
        List<Integer> l = new ArrayList<>();
        for (int i = start; i < end; i++) {
            l.add(nums[i]);
        }
        list.add(l);
        generateAllSubArrays(nums, list, start + 1, end);
    }
}

I'm getting the following result:

[[], [1], [], [1, 1], [1], [], [1, 1, 1], [1, 1], [1], [], [1, 1, 1, 1]]

Issues:

  • Some empty lists [] are present in the result (which is undesired). Unfortunately, I failed to understand why they are here.

  • Some of the expected values are absent, making the result incorrect.

What did I do wrong, and what should I do in order to get the correct computation?

I believe what I tried is using some sort of recursion, increasing space and time complexity. What would be the algorithm with the best space and time complexity?

Improve this question
0

3 Answers 3

Reset to default
3

Iterative implementation

Here's the algorithm for generating all non-empty subarrays of the given array iteratively:

  • Maintain two nested lists: one for subarrays that are in progress and the resulting list for subarrays that are already built.

  • At each iteration step, create a copy of each subarray that is still in progress and add the next element to it. Whilst the original subarray goes into the resulting list intact.

  • At the very end of the iteration, add a singleton list containing the next element into the list containing subarrays with we will continue to work, so that on the next iteration step this list would serve as a blueprint for a new subarray and immediately will go into the resulting list.

That's how it can be implemetned:

public static List<List<Integer>> getSubArrays(int[] arr) {
    List<List<Integer>> result = new ArrayList<>();
    List<List<Integer>> inProgress = new ArrayList<>();
    
    for (int next: arr) {
        List<List<Integer>> proceedWith = new ArrayList<>();
        
        for (List<Integer> subArray: inProgress) {
            result.add(subArray); // we are done with this subarray
            
            List<Integer> copy = new ArrayList<>(subArray);
            copy.add(next);
            proceedWith.add(copy); // we should continue working with copy
        }
        
        proceedWith.add(List.of(next)); // to avoid empty subarrays appear in the result
        inProgress = proceedWith;
    }
    
    result.addAll(inProgress);
    
    return result;
}

main()

public static void main(String[] args) {
    int[] arr = {1, 2, 3};
    
    getSubArrays(arr).forEach(System.out::println);
}

Output:

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

Recursive implementation

The main logic remains the same:

  • Every subarray serves as a blueprint for another subarray in case if there are some unused elements left.

  • Each single-element subarray produces a new branch of subarrays (if there are some unused elements left).

Base case (the condition when recursion should terminate) - there are no elements to explore, i.e. current index is equal to array's length.

Recursive case:

  • Create a copy of the subarray received as an argument and add the next element to, original subarray should go into the resulting list.

  • Then perform two recursive calls: one with the subarray's copy, another with a single-element subarray (containing the next element).

That's how recursive implementation might look like:

public static List<List<Integer>> getSubArraysRecursively(int[] arr) {
    
    if (arr.length == 0) return Collections.emptyList();
    
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> subarray = List.of(arr[0]);
    generateSubArrays(result, subarray, arr, 1);
    
    return result;
}

private static void generateSubArrays(List<List<Integer>> result,
                                      List<Integer> subarray,
                                      int[] arr, int i) {
    
    if (i == arr.length) { // base case
        result.add(subarray);
        return;
    }
    
    // recursive case
    result.add(subarray);

    List<Integer> copy = new ArrayList<>(subarray);
    copy.add(arr[i]);
    
    generateSubArrays(result, copy, arr, i + 1); // proceed working with the copy
    
    generateSubArrays(result, List.of(arr[i]), arr, i + 1); // start a new branch of subarrays
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Using List and stream we can get all SubArrays from an array.

public static void listSubArrays() {
    int[] array = new int[] {1, 2, 3};
    List<List<Integer>> subArrays = new ArrayList<>();
    List<Integer> list =
            Arrays.stream(array).boxed().collect(Collectors.toList());
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++){
            subArrays.add(list.subList(i, j+1));
        }
    }
    subArrays.stream().forEach(System.out::println);
}
Improve this answer

Comments

0

List#subList

You can do it with simple nested loops, a counter and some functions e.g. Math#min, List#subList etc. as shown below:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String args[]) {
        int[] arr = { 1, 1, 1, 1 };
        List<Integer> list = Arrays.stream(arr).boxed().toList();
        List<List<Integer>> result = new ArrayList<>();
        int counter = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                List<Integer> sublist = list.subList(j, Math.min(j + counter, arr.length));
                if (sublist.size() == counter)
                    result.add(sublist);
            }
            counter++;
        }

        System.out.println(result);
    }
}

Output:

[[1], [1], [1], [1], [1, 1], [1, 1], [1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1, 1]]
Improve this answer

4 Comments

[1] repeats 7 times: that's no good.
Thank you Arvind for the solution, learned a lot here! Unfortunately, the output is not what I was hoping for. Apologies for not being clear!
@Alex - That was an easy fix and you could do it. Feel free to edit posts to fix something like this. Anyway, thanks for pointing it out. I have fixed it now.
@PatPatPat - Most welcome! I wrote the answer during a meeting break 😊. I had hardly 5 minutes to write the answer and after that, I have been in back-to-back meetings. Just got time to fix it./

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.