Solving array problems effectively requires a solid understanding of the array data structure, which is a collection of elements identified by an index or key. Arrays are fundamental in programming and are widely used for solving various computational problems. Here’s a structured approach to understanding and solving array problems:
1. Understanding the Problem Statement
Before attempting to solve an array problem, it’s crucial to thoroughly understand the problem statement. Consider the following aspects:
- Input/Output: Understand what input is given (e.g., an array of integers) and what output is expected (e.g., a single integer, a new array, etc.).
- Constraints: Pay attention to constraints such as the size of the array, the range of elements, and time/space complexity requirements.
- Goal: Clearly define the goal. For example, finding the maximum sum of a subarray, sorting the array, finding a particular element, etc.
2. Analyzing the Problem
After understanding the problem statement, analyze it to determine the best approach to solve it:
- Identify Patterns: Look for patterns in the problem that could help solve it. For example, sliding window technique, two-pointer technique, or prefix sums.
- Brute Force vs. Optimal Solution: Start by thinking of a brute-force solution to understand the basics and constraints. Then, consider if there’s an optimized approach to reduce time complexity.
- Edge Cases: Consider edge cases, such as empty arrays, arrays with only one element, or arrays where all elements are the same.
Patterns
1️⃣ Interval Pattern
1 Sorting (Foundation of Most Interval Problems)
If intervals are not sorted by start time or end time. Its almost always you have to first sort them by either start time or end time.
Many interval problems start with sorting the intervals by one of the following criteria:
- Start time (used when handling problems like merging intervals or finding the minimum number of intervals to cover a range).
- End time (used when solving for problems like finding non-overlapping intervals to maximize the number of intervals).
Sorting helps to process intervals in a logical order and reduces the complexity of comparison checks.
For sorting we make use of sort function of STL library in C++.
The std::sort function is defined in the algorithm header file.
Sorting by Start Time:
If we use the std::sort function on a vector of intervals, interval could be pairs or another vector. By default it sorts by the first element (start time). This is because pairs are compared lexicographically, meaning it first compares the first element of each pair. If the first element are equal, it then compares the second elements.
// If interval are represented by pair:
vector<pair<int, int>> intervals = {{5, 10}, {1, 3}, {4, 8}, {2, 6}};
// Print the intervals
cout << "Original Intervals: ";
for (const auto& interval : intervals) {
cout << "[" << interval.first << ", " << interval.second << "] ";
}
cout << endl;
// Default sort (by strat time, first element of the pair)
sort(intervals.begin(), intervals.end());
// Print the sorted intervals
cout << "Intervals Sorted by Default (Start Time): ";
cout << "Original Intervals: ";
for (const auto& interval : intervals) {
cout << "[" << interval.first << ", " << interval.second << "] ";
}
cout << endl;We can optionally sort the interval by start time using comparator:
// Intervals are represented by pairs
vector<pair<int, int>> intervals = {{5, 10}, {1, 3}, {4, 8}, {2, 6}};
// Display the original intervals.
cout << "Original Intervals: ";
for (const auto& interval : intervals) {
cout << "[" << interval.first << ", " << interval.second << "] ";
}
cout << endl;
// Comparator function to sort by start time (first element)
bool compareByStartTime(const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first;
}
// Sort intervals by start time using a comparator
sort(intervals.begin(), intervals.end(), compareByStartTime);
// Display the sorted intervals.
cout << "Intervals Sorted by Start Time (Using Comparator): ";
for (const auto& interval : intervals) {
cout << "[" << interval.first << ", " << interval.second << "] ";
}
cout << endl;
// std::sort allows us to pass a custom comparator,
// we can directly provide a function lambda function
// instead of defining a separate function.
// Sort intervals by start time using a lambda expression
sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first < b.first; // Sort by start time
});This is equivalent to writing a custom comparator function, but it’s more concise and directly embedded within the sort function call.
Below is the scenario when the intervals are represented using vector<vector<int>> instead of vector<pair<int, int>>:
vector<vector<int>> intervals = {{5, 10}, {1, 3}, {4, 8}, {2, 6}};
// Sort using Comparator function
bool compareByStartTime(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0]; // Compare the first element (start time)
}
// Sort intervals by start time using a comparator function
sort(intervals.begin(), intervals.end(), compareByStartTime);
// Sort intervals by start time using a lambda expression
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0]; // Sort by the first element (start time)
});Sorting by End Time:
// Using vector<pair<int, int>> as the representation of intervals.
vector<pair<int, int>> intervals = {{5, 10}, {1, 3}, {4, 8}, {2, 6}};
// Comparator function to sort by end time
bool compareByEndTime(const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second; // Compare the second element (end time)
}
// Sort intervals by end time using a comparator function
sort(intervals.begin(), intervals.end(), compareByEndTime);
// Using lambda expression
// Sort intervals by end time using a lambda expression
sort(intervals.begin(), intervals.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second; // Compare the second element (end time)
});// Using vector<vector<int>> as the representation of intervals.
vector<vector<int>> intervals = {{5, 10}, {1, 3}, {4, 8}, {2, 6}};
// Comparator function to sort by end time
bool compareByEndTime(const vector<int>& a, const vector<int>& b) {
return a[1] < b[1]; // Compare the second element (end time)
}
// Sort intervals by end time using a comparator function
sort(intervals.begin(), intervals.end(), compareByEndTime);
// Using lambda expression
// Sort intervals by end time using a lambda expression
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1]; // Compare the second element (end time)
});Time Complexity for sorting the interval involves O(n log n).
2 Based on problem statement, we can classify the intervals into different scenarios:
1 No Overlapping:
Two intervals do not overlap when there is a gap between them. This means that one interval ends before the other starts.
- Condition: For two intervals
[a1, b1]and[a2, b2]:- They do not overlap if:
b1 < a2orb2 < a1
- They do not overlap if:
Example:
Interval A: [1, 2] Interval B: [3, 4] 1-----2 3-----4
2 Complete Overlapping:
One interval completely contains another interval. The start and end points of the contained interval are within the boundaries of the containing interval.
- Condition: For two interval
[a1, b1]and[a2, b2]:- Interval
Acompletely overlaps IntervalBif:a1 ≤ a2andb1 ≥ b2
- Interval
Example:
Interval A: [1, 5] Interval B: [2, 3] 1---------------5 2-----3
3 Partial Overlapping:
Two intervals partially overlaps when they share some common points but neither completely contains the other.
- Condition: For two intervals
[a1, b1]and[a2, b2]:- They partially overlap if:
a1 < b2anda2 < b1
- They partially overlap if:
Example:
Interval 1: [1, 5] Interval 2: [4, 6] 1-----------5 4-------6
2️⃣ Prefix Sum (Cumulative Sum)
The prefix sum technique, also known as cumulative sum, is used to efficiently compute the sum of elements in an array up to a given index. By pre-computing the sum of all elements from the start of the array to each index, this method allows for quick calculation of the sum of any subarray. It is particularly useful in solving computational problems like range sum queries and in dynamic programming, where repeated sum calculations can be optimized using these pre-computed values.
Time and Space Complexity:
- The time complexity of the Prefix Sum is
O(n), wherenis the number of elements in the array. - The space complexity of the Prefix Sum is
O(n), wherenis the number of element in the array.- This is because we are constructing a new array.
- We can reduce it to constant space if we modify the input array only. However this thing depends on the use cases.
Let's say you have the following array arr:
arr = [2, 8, 3, 9, 6, 5, 4]The prefix sum for the arr would be:
prefixSum = [2, 10, 13, 22, 28, 33, 37]This is how it is constructed:
We can construct a new array or change in current one. For the sake of current example, we would construct a new array, named as prefixSum.
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
prefixSum[0] = arr[0]Iterate from 1 to last element:
First Iteration:
i = 1
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[1] = prefixSum[0] + arr[1]
prefixSum[1] = 2 + 8
= 10Second Iteration:
i = 2
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[2] = prefixSum[1] + arr[2]
prefixSum[2] = 10 + 3
= 13Third Iteration:
i = 3
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | 13 | | | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[3] = prefixSum[2] + arr[3]
prefixSum[3] = 13 + 9
= 22Fourth Iteration:
i = 4
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | 13 | 22 | | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[4] = prefixSum[3] + arr[4]
prefixSum[4] = 22 + 6
= 28Fifth Iteration:
i = 5
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | 13 | 22 | 28 | | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[5] = prefixSum[4] + arr[5]
prefixSum[5] = 28 + 5
= 33Sixth Iteration:
i = 6
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | 13 | 22 | 28 | 33 | |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
i
prefix sum of current index = prefix sum of previous index + current index value
prefixSum[6] = prefixSum[5] + arr[6]
prefixSum[6] = 33 + 4
= 37Final Values:
+-----+-----+-----+-----+-----+-----+-----+
prefixSum = | 2 | 10 | 13 | 22 | 28 | 33 | 37 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
arr = | 2 | 8 | 3 | 9 | 6 | 5 | 4 |
+-----+-----+-----+-----+-----+-----+-----+| Index | Array Element | Prefix Sum |
|---|---|---|
| 0 | 2 | 2 |
| 1 | 8 | 2 + 8 = 10 |
| 2 | 3 | 10 + 3 = 13 |
| 3 | 9 | 13 + 9 = 22 |
| 4 | 6 | 22 + 6 = 28 |
| 5 | 5 | 28 + 5 = 33 |
| 6 | 4 | 33 + 4 = 37 |
Where to Apply this Approach❔
We can apply this approach in problems related to Subarray, problems where we are asked to:
- Count the subarrays with some condition
- Find Maximum length Subarray with some condition
- Check if subarray exists with some given condition
Mainly the problem dealing with Subarray sum.
Approach works on the following principle:
- If the prefix sum up to
ithindex isX, and the prefix sum up tojthindex isYand it is found thatY = X +k, then the required subarray is found withias start index andjas end index. - If the sum of elements from the start of the array up to index
iisX(called the prefix sum), and the sum of elements from the start up to indexjisY(another prefix sum), and it is found that:y = x + k- This means that the sum of the elements between
i + 1andjis equal tok. So, the subarray with sumkstarts just after indexiand at indexj. - To efficiently track these prefix sums and their corresponding indices, we can use a hashmap. The hashmap will store:
- Key: The prefix sum up to a certain index.
- Value: The index where that prefix sum occurred.
Why we need this approach of Hashmap + Prefix Sum ?
So basically for subarray related problems Brute Force method takes O(n^2) time to process each subarray + extra time in processing .
But with this approach only O(n) time is taken .
Now you might wonder that what is stopping you from using Sliding window approach for such problems
Sliding window is only applicable when we know for sure if the prefixsum is an increasing or decreasing function(i.e. Monotonous in nature)
So for problems where negative input is given this approach of PrefixSum + Hashmap is the best way to solve such problems.