Mathematics

Generating all subarrays of an array

In the realm of computer science and programming, understanding arrays and their subarrays is a fundamental concept. Subarrays are contiguous portions of an array that can be analyzed individually. The task of generating all possible subarrays of an array is not only an important programming exercise but also finds applications in various algorithmic problems.

Problem Statement

Given an array, the problem entails generating and printing all possible subarrays of the given array. A subarray is defined by two indices, the starting index (inclusive) and the ending index (exclusive), within the original array. The goal is to systematically extract and print all subarrays of varying lengths, beginning from each index of the array.

Example and Description

Let's illustrate the problem with a simple example. Consider the array [1, 2, 3, 6]. The task is to generate all subarrays and print their elements.

Step 1

Start with index 0. Generate subarrays starting from index 0:

Subarray: [1]
Subarray: [1, 2]
Subarray: [1, 2, 3]
Subarray: [1, 2, 3, 6]

Step 2

Move to index 1. Generate subarrays starting from index 1:

Subarray: [2]
Subarray: [2, 3]
Subarray: [2, 3, 6]

Step 3

Move to index 2. Generate subarrays starting from index 2:

Subarray: [3]
Subarray: [3, 6]

Step 4

Move to index 3. Generate subarrays starting from index 3:

Subarray: [6]

Combine all the generated subarrays to get the complete list of subarrays: [1], [1, 2], [1, 2, 3], [1, 2, 3, 6], [2], [2, 3], [2, 3, 6], [3], [3, 6], [6].

Idea to Solve

The problem can be solved by using two nested loops. The outer loop iterates through each index of the array, and the inner loop generates subarrays starting from the current index to the end of the array. A separate function can be defined to print the elements of a given subarray.

Standard Pseudocode

function printSubarray(arr, start, last)
    for i = start to last - 1
        print arr[i]
    end for
end function

function findSubArray(arr, n)
    for i = 0 to n - 1
        for j = i + 1 to n
            printSubarray(arr, i, j)
        end for
    end for
end function

main
    arr1 = [1, 2, 3, 6]
    arr2 = [7, 8, 1, 6, 4]
    n = size of arr1
    findSubArray(arr1, n)
    n = size of arr2
    findSubArray(arr2, n)
end main

Algorithm Explanation

Define the printSubarray function that takes an array arr, a starting index start, and an ending index last as parameters. This function prints the elements of the subarray from index start to last - 1.
Define the findSubArray function that takes an array arr and its length n as parameters. This function generates and prints all subarrays of the given array.
- The outer loop iterates through each index i from 0 to n - 1.
- The inner loop iterates through each index j from i + 1 to n.
- Within the inner loop, the printSubarray function is called to print the subarray from index i to j - 1.
In the main function, define the arrays arr1 and arr2 with their respective elements.
Calculate the size of the arrays using the sizeof operator and the size of an individual element.
Call the findSubArray function for both arr1 and arr2.

Code Solution

// C Program
// Generating all subarrays of an array
#include <stdio.h>

// Print resultant subarray
void printSubarray(int arr[], int start, int last)
{
    for (int i = start; i < last; ++i)
    {
        printf("  %d", arr[i]);
    }
    printf("\n");
}
void findSubArray(int arr[], int n)
{
    // Execute this loop through by array length
    for (int i = 0; i < n; ++i)
    {
        // Inner loop from i+1 to n
        for (int j = i + 1; j <= n; ++j)
        {
            // Print subarray in range [i..j]
            printSubarray(arr, i, j);
        }
    }
}
int main(int argc, char const *argv[])
{
    int arr1[] = {
        1 , 2 , 3 , 6
    };
    int arr2[] = {
        7 , 8 , 1 , 6 , 4
    };
    // Test Case A
    int n = sizeof(arr1) / sizeof(arr1[0]);
    findSubArray(arr1, n);
    printf("\n");
    // Test Case B
    n = sizeof(arr2) / sizeof(arr2[0]);
    findSubArray(arr2, n);
    return 0;
}

input

  1
  1  2
  1  2  3
  1  2  3  6
  2
  2  3
  2  3  6
  3
  3  6
  6

  7
  7  8
  7  8  1
  7  8  1  6
  7  8  1  6  4
  8
  8  1
  8  1  6
  8  1  6  4
  1
  1  6
  1  6  4
  6
  6  4
  4

// Java program for
// Generating all subarrays of an array
import java.util.ArrayList;
public class Subarrays
{
	// Print resultant subarray
	public void printSubarray(int[] arr, int start, int last)
	{
		for (int i = start; i < last; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	public void findSubArray(int[] arr, int n)
	{
		// Execute this loop through by array length
		for (int i = 0; i < n; ++i)
		{
			// Inner loop from i+1 to n
			for (int j = i + 1; j <= n; ++j)
			{
				// Print subarray in range [i..j]
				printSubarray(arr, i, j);
			}
		}
	}
	public static void main(String[] args)
	{
		Subarrays task = new Subarrays();
		int[] arr1 = {
			1 , 2 , 3 , 6
		};
		int[] arr2 = {
			7 , 8 , 1 , 6 , 4
		};
		// Test Case A
		int n = arr1.length;
		task.findSubArray(arr1, n);
		System.out.print("\n");
		// Test Case B
		n = arr2.length;
		task.findSubArray(arr2, n);
	}
}

input

// Include header file
#include <iostream>
using namespace std;

class Subarrays
{
	public:
		// Print resultant subarray
		void printSubarray(int arr[], int start, int last)
		{
			for (int i = start; i < last; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	void findSubArray(int arr[], int n)
	{
		// Execute this loop through by array length
		for (int i = 0; i < n; ++i)
		{
			// Inner loop from i+1 to n
			for (int j = i + 1; j <= n; ++j)
			{
				// Print subarray in range [i..j]
				this->printSubarray(arr, i, j);
			}
		}
	}
};
int main()
{
	Subarrays *task = new Subarrays();
	int arr1[] = {
		1 , 2 , 3 , 6
	};
	int arr2[] = {
		7 , 8 , 1 , 6 , 4
	};
	// Test Case A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	task->findSubArray(arr1, n);
	cout << "\n";
	// Test Case B
	n = sizeof(arr2) / sizeof(arr2[0]);
	task->findSubArray(arr2, n);
	return 0;
}

input

// Include namespace system
using System;
public class Subarrays
{
	// Print resultant subarray
	public void printSubarray(int[] arr, int start, int last)
	{
		for (int i = start; i < last; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void findSubArray(int[] arr, int n)
	{
		// Execute this loop through by array length
		for (int i = 0; i < n; ++i)
		{
			// Inner loop from i+1 to n
			for (int j = i + 1; j <= n; ++j)
			{
				// Print subarray in range [i..j]
				this.printSubarray(arr, i, j);
			}
		}
	}
	public static void Main(String[] args)
	{
		Subarrays task = new Subarrays();
		int[] arr1 = {
			1 , 2 , 3 , 6
		};
		int[] arr2 = {
			7 , 8 , 1 , 6 , 4
		};
		// Test Case A
		int n = arr1.Length;
		task.findSubArray(arr1, n);
		Console.Write("\n");
		// Test Case B
		n = arr2.Length;
		task.findSubArray(arr2, n);
	}
}

input

<?php
class Subarrays
{
	// Print resultant subarray
	public	function printSubarray($arr, $start, $last)
	{
		for ($i = $start; $i < $last; ++$i)
		{
			echo(" ".$arr[$i]);
		}
		echo("\n");
	}
	public	function findSubArray($arr, $n)
	{
		// Execute this loop through by array length
		for ($i = 0; $i < $n; ++$i)
		{
			// Inner loop from i+1 to n
			for ($j = $i + 1; $j <= $n; ++$j)
			{
				// Print subarray in range [i..j]
				$this->printSubarray($arr, $i, $j);
			}
		}
	}
}

function main()
{
	$task = new Subarrays();
	$arr1 = array(1, 2, 3, 6);
	$arr2 = array(7, 8, 1, 6, 4);
	// Test Case A
	$n = count($arr1);
	$task->findSubArray($arr1, $n);
	echo("\n");
	// Test Case B
	$n = count($arr2);
	$task->findSubArray($arr2, $n);
}
main();

input

class Subarrays
{
	// Print resultant subarray
	printSubarray(arr, start, last)
	{
		for (var i = start; i < last; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	findSubArray(arr, n)
	{
		// Execute this loop through by array length
		for (var i = 0; i < n; ++i)
		{
			// Inner loop from i+1 to n
			for (var j = i + 1; j <= n; ++j)
			{
				// Print subarray in range [i..j]
				this.printSubarray(arr, i, j);
			}
		}
	}
}

function main()
{
	var task = new Subarrays();
	var arr1 = [1, 2, 3, 6];
	var arr2 = [7, 8, 1, 6, 4];
	// Test Case A
	var n = arr1.length;
	task.findSubArray(arr1, n);
	process.stdout.write("\n");
	// Test Case B
	n = arr2.length;
	task.findSubArray(arr2, n);
}
main();

input

class Subarrays :
	#  Print resultant subarray
	def printSubarray(self, arr, start, last) :
		i = start
		while (i < last) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def findSubArray(self, arr, n) :
		#  Execute this loop through by list length
		i = 0
		while (i < n) :
			#  Inner loop from i+1 to n
			j = i + 1
			while (j <= n) :
				#  Print sublist in range [i..j]
				self.printSubarray(arr, i, j)
				j += 1
			
			i += 1
		
	

def main() :
	task = Subarrays()
	arr1 = [1, 2, 3, 6]
	arr2 = [7, 8, 1, 6, 4]
	#  Test Case A
	n = len(arr1)
	task.findSubArray(arr1, n)
	print(end = "\n")
	#  Test Case B
	n = len(arr2)
	task.findSubArray(arr2, n)

if __name__ == "__main__": main()

input

  1
  1  2
  1  2  3
  1  2  3  6
  2
  2  3
  2  3  6
  3
  3  6
  6

  7
  7  8
  7  8  1
  7  8  1  6
  7  8  1  6  4
  8
  8  1
  8  1  6
  8  1  6  4
  1
  1  6
  1  6  4
  6
  6  4
  4

class Subarrays 
	#  Print resultant subarray
	def printSubarray(arr, start, last) 
		i = start
		while (i < last) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	def findSubArray(arr, n) 
		i = 0
		#  Execute this loop through by array length
		while (i < n) 
			
			j = i + 1
			#  Inner loop from i+1 to n
			while (j <= n) 
				#  Print subarray in range [i..j]
				self.printSubarray(arr, i, j)
				j += 1
			end

			i += 1
		end

	end

end

def main() 
	task = Subarrays.new()
	arr1 = [1, 2, 3, 6]
	arr2 = [7, 8, 1, 6, 4]
	#  Test Case A
	n = arr1.length
	task.findSubArray(arr1, n)
	print("\n")
	#  Test Case B
	n = arr2.length
	task.findSubArray(arr2, n)
end

main()

input

class Subarrays()
{
	// Print resultant subarray
	def printSubarray(arr: Array[Int], start: Int, last: Int): Unit = {
		var i: Int = start;
		while (i < last)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def findSubArray(arr: Array[Int], n: Int): Unit = {
		
		var i: Int = 0;
      	// Execute this loop through by array length
		while (i < n)
		{
			
			var j: Int = i + 1;
          	// Inner loop from i+1 to n
			while (j <= n)
			{
				// Print subarray in range [i..j]
				printSubarray(arr, i, j);
				j += 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarrays = new Subarrays();
		var arr1: Array[Int] = Array(1, 2, 3, 6);
		var arr2: Array[Int] = Array(7, 8, 1, 6, 4);
		// Test Case A
		var n: Int = arr1.length;
		task.findSubArray(arr1, n);
		print("\n");
		// Test Case B
		n = arr2.length;
		task.findSubArray(arr2, n);
	}
}

input

import Foundation;
class Subarrays
{
	// Print resultant subarray
	func printSubarray(_ arr: [Int], _ start: Int, _ last: Int)
	{
		var i = start;
		while (i < last)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func findSubArray(_ arr: [Int], _ n: Int)
	{
		// Execute this loop through by array length
		var i = 0;
		while (i < n)
		{
			// Inner loop from i+1 to n
			var j = i + 1;
			while (j <= n)
			{
				// Print subarray in range [i..j]
				self.printSubarray(arr, i, j);
				j += 1;
			}
			i += 1;
		}
	}
}
func main()
{
	let task = Subarrays();
	let arr1 = [1, 2, 3, 6];
	let arr2 = [7, 8, 1, 6, 4];
	// Test Case A
	var n = arr1.count;
	task.findSubArray(arr1, n);
	print(terminator: "\n");
	// Test Case B
	n = arr2.count;
	task.findSubArray(arr2, n);
}
main();

input

  1
  1  2
  1  2  3
  1  2  3  6
  2
  2  3
  2  3  6
  3
  3  6
  6

  7
  7  8
  7  8  1
  7  8  1  6
  7  8  1  6  4
  8
  8  1
  8  1  6
  8  1  6  4
  1
  1  6
  1  6  4
  6
  6  4
  4

class Subarrays
{
	// Print resultant subarray
	fun printSubarray(arr: Array < Int > , start: Int, last: Int): Unit
	{
		var i: Int = start;
		while (i < last)
		{
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	fun findSubArray(arr: Array < Int > , n: Int): Unit
	{
		
		var i: Int = 0;
      	// Execute this loop through by array length
		while (i < n)
		{
			
			var j: Int = i + 1;
          	// Inner loop from i+1 to n
			while (j <= n)
			{
				// Print subarray in range [i..j]
				this.printSubarray(arr, i, j);
				j += 1;
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarrays = Subarrays();
	val arr1: Array < Int > = arrayOf(1, 2, 3, 6);
	val arr2: Array < Int > = arrayOf(7, 8, 1, 6, 4);
	// Test Case A
	var n: Int = arr1.count();
	task.findSubArray(arr1, n);
	print("\n");
	// Test Case B
	n = arr2.count();
	task.findSubArray(arr2, n);
}

input

Time Complexity

The time complexity of the solution is O(n^3), where 'n' is the length of the input array. This is because the two nested loops run in O(n^2) time, and within the innermost loop, the printSubarray function takes O(n) time in the worst case (printing a subarray of length 'n').

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment

Name