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 arrayarr
, a starting indexstart
, and an ending indexlast
as parameters. This function prints the elements of the subarray from indexstart
tolast - 1
. - Define the
findSubArray
function that takes an arrayarr
and its lengthn
as parameters. This function generates and prints all subarrays of the given array.- The outer loop iterates through each index
i
from 0 ton - 1
. - The inner loop iterates through each index
j
fromi + 1
ton
. - Within the inner loop, the
printSubarray
function is called to print the subarray from indexi
toj - 1
.
- The outer loop iterates through each index
- In the
main
function, define the arraysarr1
andarr2
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 botharr1
andarr2
.
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
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
// 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
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
// 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
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
<?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
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
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
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(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
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: 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
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
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
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
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').
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