Welcome back to crafting your own Algorithm for the first time
🎯 Design Example 3: "Product of Array Except Self"
Problem: Given array, return array where each element is the product of all others.
Constraint: Cannot use division, must be O(n) time!
Step 1: Understand
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Why?
output[0] = 2 × 3 × 4 = 24
output[1] = 1 × 3 × 4 = 12
output[2] = 1 × 2 × 4 = 8
output[3] = 1 × 2 × 3 = 6
Step 2: Explore by Hand
Array: [1, 2, 3, 4]
Index: 0 1 2 3
For index 0: product of [2,3,4]
For index 1: product of [1,3,4]
For index 2: product of [1,2,4]
For index 3: product of [1,2,3]
Naive approach: nested loops O(n²)
for i in array:
product = 1
for j in array:
if j != i:
product *= array[j]
Can we do better? Let's think differently...
Step 3: Pattern Recognition
Breakthrough insight: Each element's answer is:
Product of everything to the LEFT × Product of everything to the RIGHT
Index i result = (product of [0...i-1]) × (product of [i+1...n])
Visual pattern:
Array: [1, 2, 3, 4]
Index: 0 1 2 3
For index 1:
Left product = 1 (elements before index 1)
Right product = 3 × 4 = 12 (elements after index 1)
Result = 1 × 12 = 12 ✓
For index 2:
Left product = 1 × 2 = 2
Right product = 4
Result = 2 × 4 = 8 ✓
Two-pass pattern:
Pass 1 (left to right): Build left products
Pass 2 (right to left): Build right products
Left products: [1, 1, 2, 6]
Array: [1, 2, 3, 4]
Right products: [24, 12, 4, 1]
Result: [24, 12, 8, 6]
Step 4: Design Your Algorithm
Decision 1: Two-pass approach
- First pass: accumulate products from left
- Second pass: accumulate products from right
Decision 2: Optimize space
- Can we do this without extra arrays?
- Yes! Build result array progressively
#include <iostream>
#include <vector>
using namespace std;
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, 1);
// Pass 1: Build left products
int leftProduct = 1;
for (int i = 0; i < n; i++) {
result[i] = leftProduct;
leftProduct *= nums[i];
}
// Pass 2: Multiply by right products
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= rightProduct;
rightProduct *= nums[i];
}
return result;
}
int main() {
vector<int> nums = {1, 2, 3, 4};
vector<int> result = productExceptSelf(nums);
cout << "Result: ";
for (int x : result) {
cout << x << " ";
}
// Output: 24 12 8 6
return 0;
}
Step 5: Optimize & Analyze
Time Complexity:
- Pass 1 (left products): O(n)
- Pass 2 (right products): O(n)
- Total: O(n) ✓ Meets constraint!
Space Complexity:
- Result array: O(n) (required for output)
- Extra space: O(1) (just two variables)
- ✓ Optimal space!
Why this is clever:
- No division needed
- No extra arrays (beyond output)
- Only two passes
- Each pass does O(n) work
Detailed Visualization:
Array: [1, 2, 3, 4]
Pass 1 - Building left products:
i=0: result[0] = 1 (no elements to left)
leftProduct = 1 × 1 = 1
i=1: result[1] = 1 (product of [1])
leftProduct = 1 × 2 = 2
i=2: result[2] = 2 (product of [1,2])
leftProduct = 2 × 3 = 6
i=3: result[3] = 6 (product of [1,2,3])
leftProduct = 6 × 4 = 24
After pass 1: result = [1, 1, 2, 6]
Pass 2 - Multiplying right products:
i=3: result[3] = 6 × 1 = 6 (no elements to right)
rightProduct = 1 × 4 = 4
i=2: result[2] = 2 × 4 = 8 (product of [4])
rightProduct = 4 × 3 = 12
i=1: result[1] = 1 × 12 = 12 (product of [3,4])
rightProduct = 12 × 2 = 24
i=0: result[0] = 1 × 24 = 24 (product of [2,3,4])
rightProduct = 24 × 1 = 24
After pass 2: result = [24, 12, 8, 6] ✓
🔥 Real Interview Example: "Meeting Rooms II"
Problem: Given meeting time intervals, find minimum number of conference rooms needed.
Input: [[0,30], [5,10], [15,20]]
Output: 2
Explanation:
Room 1: [0,30]
Room 2: [5,10], [15,20]
The Design Process
Step 1: Understand
Timeline visualization:
0 5 10 15 20 30
|------ Meeting 1 -----------|
|--Meeting 2--|
|--Meeting 3--|
At time 5: 2 meetings overlap → need 2 rooms
At time 15: Meeting 2 done, Meeting 3 starts → still 2 rooms
Step 2: Explore
Track events:
Time 0: Meeting starts → rooms needed = 1
Time 5: Meeting starts → rooms needed = 2
Time 10: Meeting ends → rooms needed = 1
Time 15: Meeting starts → rooms needed = 2
Time 20: Meeting ends → rooms needed = 1
Time 30: Meeting ends → rooms needed = 0
Maximum rooms needed = 2
Step 3: Pattern
Key insight: Separate start and end times!
Starts: [0, 5, 15]
Ends: [10, 20, 30]
Process chronologically:
- When meeting starts: rooms_needed++
- When meeting ends: rooms_needed--
- Track maximum
Step 4: Design
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minMeetingRooms(vector<vector<int>>& intervals) {
vector<int> starts, ends;
// Separate start and end times
for (auto& interval : intervals) {
starts.push_back(interval[0]);
ends.push_back(interval[1]);
}
// Sort both arrays
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, maxRooms = 0;
int s = 0, e = 0;
// Process events chronologically
while (s < starts.size()) {
if (starts[s] < ends[e]) {
// Meeting starts before earliest end
rooms++;
maxRooms = max(maxRooms, rooms);
s++;
} else {
// Meeting ends
rooms--;
e++;
}
}
return maxRooms;
}
int main() {
vector<vector<int>> meetings = {{0,30}, {5,10}, {15,20}};
cout << "Minimum rooms needed: " << minMeetingRooms(meetings) << endl;
// Output: 2
return 0;
}
Step 5: Optimize
Time: O(n log n) for sorting
Space: O(n) for separate arrays
Creative insight:
- Instead of tracking overlaps (O(n²))
- We track event timeline (O(n log n))
- This is the "sweep line" algorithm pattern!
Visual:
Timeline: ────────────────────────────►
Events: S S E S E E
Rooms: 1 2 1 2 1 0
↑
Maximum = 2
Let's Jump to the Final Part of our journey
Top comments (0)