Problem

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

Examples

Example 1:

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

Java
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]]
    }
}
Python
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)