Problem

Given an array write an algorithm to get or print all the possible sub arrays.

Examples

Example 1:

1
2

Input: arr: [1, 2, 3]
Output: [[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

Solution

Method 1 - Using nested loops and changing array size

To find all possible subarrays of a given array, we can use a simple nested loop approach:

  1. Initialize Result List: Create an empty list to store all the subarrays.
  2. Outer Loop: The outer loop iterates through the starting indices of the subarrays.
  3. Inner Loop: The inner loop iterates through the ending indices of the subarrays, starting from the current start index.
  4. Collect Subarray: For each pair of start and end indices, collect the subarray elements and add them to the result list.
  5. Return Result: Finally, return the result list containing all subarrays.

This straightforward approach ensures that we generate all possible subarrays by systematically considering each starting and ending index pair.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Solution {
    public List<List<Integer>> getAllSubarrays(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        int n = arr.length;

        // Outer loop to fix the start index
        for (int i = 0; i < n; i++) {
            // Inner loop to fix the end index
            for (int j = i; j < n; j++) {
                List<Integer> subarray = new ArrayList<>();
                // Collecting subarray from i to j
                for (int k = i; k <= j; k++) {
                    subarray.add(arr[k]);
                }
                result.add(subarray);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 2, 3};
        List<List<Integer>> subarrays = solution.getAllSubarrays(arr);
        System.out.println(subarrays); // Expected output: [[1], [1, 2], [1, 2,
                                       // 3], [2], [2, 3], [3]]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def getAllSubarrays(self, arr: List[int]) -> List[List[int]]:
        result = []
        n = len(arr)

        # Outer loop to fix the start index
        for i in range(n):
            # Inner loop to fix the end index
            for j in range(i, n):
                subarray = []
                # Collecting subarray from i to j
                for k in range(i, j + 1):
                    subarray.append(arr[k])
                result.append(subarray)

        return result

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(n^3)