Subarray Examples in DSA
A subarray is a contiguous part of an array. For example, if arr = [1, 2, 3], then possible
subarrays are [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]. Subarrays are always continuous; non-
contiguous elements form a subsequence, not a subarray.
Example 1: Print All Subarrays
Problem: Given an array, print all its subarrays.
Algorithm:
1. Iterate over all possible starting indices i.
2. For each i, iterate over all possible ending indices j.
3. Print elements from arr[i] to arr[j].
• C++ Code:
#include <iostream>
using namespace std;
void printSubarrays(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
cout << arr[k] << " ";
}
cout << endl;
}
}
}
int main() {
int arr[] = {1, 2, 3};
int n = 3;
printSubarrays(arr, n);
return 0;
}
Explanation: The outer loop picks start index i, middle loop picks end index j, and inner loop
prints elements from i to j. Total subarrays = n*(n+1)/2.
Example 2: Maximum Subarray Sum (Kadane’s Algorithm)
Problem: Find the maximum sum of any subarray in a given array.
• C++ Code:
#include <iostream>
#include <climits>
using namespace std;
int kadane(int arr[], int n) {
int max_so_far = arr[0];
int current_max = arr[0];
for (int i = 1; i < n; i++) {
current_max = max(arr[i], current_max + arr[i]);
max_so_far = max(max_so_far, current_max);
}
return max_so_far;
}
int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
cout << "Maximum Subarray Sum = " << kadane(arr, n);
return 0;
}
Explanation: Kadane’s algorithm tracks the maximum sum ending at each position and
updates the global maximum. It runs in O(n) time.
Example 3: Count Subarrays with Sum = K
Problem: Count how many subarrays have a sum equal to K using prefix sum and hash map.
• C++ Code:
#include <iostream>
#include <unordered_map>
using namespace std;
int countSubarraysWithSumK(int arr[], int n, int K) {
unordered_map<int, int> mp;
int count = 0, sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == K)
count++;
if ([Link](sum - K) != [Link]())
count += mp[sum - K];
mp[sum]++;
}
return count;
}
int main() {
int arr[] = {1, 2, 3};
int n = 3, K = 3;
cout << "Count of Subarrays with Sum " << K << " = " <<
countSubarraysWithSumK(arr, n, K);
return 0;
}
Explanation: For each prefix sum, check if (sum - K) exists in the map. If yes, there is a
subarray with sum K.
Example 4: Longest Subarray with Sum = K
Problem: Find the length of the longest subarray whose sum equals K using prefix sums.
• C++ Code:
#include <iostream>
#include <unordered_map>
using namespace std;
int longestSubarrayWithSumK(int arr[], int n, int K) {
unordered_map<int, int> mp;
int sum = 0, maxLen = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == K)
maxLen = i + 1;
if ([Link](sum - K) != [Link]())
maxLen = max(maxLen, i - mp[sum - K]);
if ([Link](sum) == [Link]())
mp[sum] = i;
}
return maxLen;
}
int main() {
int arr[] = {10, 5, 2, 7, 1, 9};
int n = 6, K = 15;
cout << "Longest Subarray Length with Sum " << K << " = " <<
longestSubarrayWithSumK(arr, n, K);
return 0;
}
Explanation: Uses prefix sum and hashmap to track first occurrences of sums. Time
complexity is O(n).
Summary
Problem Algorithm Time Complexity
Print all subarrays 3 nested loops O(n³)
Max subarray sum Kadane’s algorithm O(n)
Count subarrays with sum K Prefix Sum + HashMap O(n)
Longest subarray with sum K Prefix Sum + HashMap O(n)