The Art of Creating Solutions from Scratch
"Every algorithm you've ever used was once just an idea in someone's mind."
Now it's your turn to create.
After mastering the time vs space trade-off, you understand the tools. Now comes the creative part: designing your own algorithms. This is where programming transforms from following recipes to crafting solutions—the intersection of logic, creativity, and craft.
🧠 What Makes Algorithm Design Creative?
Algorithm design isn't just technical—it's an art form:
Mathematics Programming Creative Writing
↓ ↓ ↓
Proof Algorithm Story Arc
Logic Optimization Plot Structure
Patterns Trade-offs Character Development
↓ ↓ ↓
All require: CREATIVE PROBLEM-SOLVING
When you write an algorithm, you're:
- 🎯 Identifying patterns others haven't seen
- 🔄 Making trade-off decisions based on constraints
- 🏗️ Building abstractions that elegantly solve problems
- ✨ Inventing techniques that become tools for others
📐 The 5-Step Algorithm Design Framework
┌─────────────────────────────────────────────┐
│ 1. UNDERSTAND → What exactly are we │
│ solving? │
├─────────────────────────────────────────────┤
│ 2. EXPLORE → Try simple examples │
│ by hand │
├─────────────────────────────────────────────┤
│ 3. PATTERN → What repeats? What │
│ changes? │
├─────────────────────────────────────────────┤
│ 4. DESIGN → Choose your approach │
│ & data structures │
├─────────────────────────────────────────────┤
│ 5. OPTIMIZE → Refine time & space │
│ complexity │
└─────────────────────────────────────────────┘
Let's see this process in action.
🎯 Design Example 1: "First Unique Character"
Problem: Given a string, find the first character that appears only once.
Step 1: Understand
Input: "leetcode"
Output: 'l' (appears once, first in string)
Input: "loveleetcode"
Output: 'v' (l appears twice, o appears twice, v is first unique)
Input: "aabb"
Output: null (no unique character)
What we need:
- Track how many times each character appears
- Remember the order we saw them
- Find the first one with count = 1
Step 2: Explore by Hand
String: "leetcode"
Manual process:
l → Count it
e → Count it
e → Count it (now e=2)
t → Count it
...
After counting:
l: 1 ✓
e: 3
t: 1 ✓
c: 1 ✓
o: 1 ✓
d: 1 ✓
Scan left to right: l appears first → return 'l'
Pattern discovered: We need TWO passes!
- Count frequencies
- Find first with frequency = 1
Step 3: Pattern Recognition
Pass 1: Build frequency map
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ l │ e │ e │ t │ c │ o │ d │ e │
└───┴───┴───┴───┴───┴───┴───┴───┘
↓
{l:1, e:3, t:1, c:1, o:1, d:1}
Pass 2: Scan original string
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ l │ e │ e │ t │ c │ o │ d │ e │
└───┴───┴───┴───┴───┴───┴───┴───┘
↓
Check freq[l] = 1 ✓ Return 'l'
Step 4: Design Your Algorithm
Decision 1: Data Structure
- Need frequency counting → Hash map
- Need to preserve order → Scan original string
Decision 2: Approach
- Two-pass algorithm (cleaner than one-pass with complex logic)
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
char firstUniqChar(string s) {
// Step 1: Count frequencies
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
// Step 2: Find first unique
for (char c : s) {
if (freq[c] == 1) {
return c;
}
}
return '\0'; // No unique character
}
int main() {
cout << "Test 1: " << firstUniqChar("leetcode") << endl; // 'l'
cout << "Test 2: " << firstUniqChar("loveleetcode") << endl; // 'v'
cout << "Test 3: " << firstUniqChar("aabb") << endl; // '\0'
return 0;
}
Step 5: Optimize & Analyze
Time Complexity:
- Pass 1 (counting): O(n)
- Pass 2 (finding): O(n)
- Total: O(n)
Space Complexity:
- Hash map: O(26) for lowercase letters = O(1)
- Or O(k) for k unique characters
Can we do better?
- Time: No, must scan entire string at least once
- Space: No, must store frequencies somehow
✓ This is optimal!
Visualization:
"leetcode"
↓↓↓↓↓↓↓↓ First pass: Build frequency
{l:1, e:3, t:1, c:1, o:1, d:1}
"leetcode"
↓ Second pass: Find first with freq=1
l (freq=1) → Found! ✓
Time: O(n) + O(n) = O(n)
Space: O(1) for fixed alphabet
🎯 Design Example 2: "Merge Intervals"
Problem: Given intervals, merge all overlapping ones.
Step 1: Understand
Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Why?
[1,3] and [2,6] overlap → merge to [1,6]
[8,10] doesn't overlap with others
[15,18] doesn't overlap with others
Step 2: Explore by Hand
Intervals: [1,3] [2,6] [8,10] [15,18]
Visual timeline:
0 5 10 15 20
|-------| |---| (1,3)
|---------| (2,6)
|---| (8,10)
|---| (15,18)
Observation: If sorted by start time, we can merge adjacent overlaps!
After sorting by start:
[1,3] [2,6] [8,10] [15,18] (already sorted)
Compare pairs:
[1,3] vs [2,6]: 3 ≥ 2 → overlap! → merge to [1,6]
[1,6] vs [8,10]: 6 < 8 → no overlap
[8,10] vs [15,18]: 10 < 15 → no overlap
Step 3: Pattern Recognition
Key insight: Overlapping intervals have:
Interval A: [start_A, end_A]
Interval B: [start_B, end_B]
Overlap if: end_A ≥ start_B (when A comes before B)
Merge strategy:
new_start = start_A
new_end = max(end_A, end_B)
Pattern:
Sort → Compare adjacent → Merge if overlap
[1,3][2,6][8,10]
↓ ↓
Overlap!
Merge → [1,6]
[1,6][8,10]
↓ ↓
No overlap
Keep both
Step 4: Design Your Algorithm
Decision 1: Sort first
- Sorting by start time makes comparisons simple
- Only need to check adjacent intervals
Decision 2: Track current merged interval
- Extend it when overlap found
- Add to result when no overlap
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// Step 1: Sort by start time
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
vector<int> current = intervals[0];
// Step 2: Merge overlapping intervals
for (int i = 1; i < intervals.size(); i++) {
if (current[1] >= intervals[i][0]) {
// Overlap! Extend current interval
current[1] = max(current[1], intervals[i][1]);
} else {
// No overlap, save current and start new
result.push_back(current);
current = intervals[i];
}
}
// Don't forget the last interval!
result.push_back(current);
return result;
}
int main() {
vector<vector<int>> intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
vector<vector<int>> merged = merge(intervals);
cout << "Merged intervals: ";
for (auto& interval : merged) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
return 0;
}
Step 5: Optimize & Analyze
Time Complexity:
- Sorting: O(n log n)
- Merging: O(n)
- Total: O(n log n)
Space Complexity:
- Result array: O(n) worst case (no merges)
- Sorting: O(log n) stack space
Can we do better?
- Time: No, sorting is necessary to identify overlaps efficiently
- Without sorting: O(n²) to compare all pairs
✓ O(n log n) is optimal for comparison-based approach
Visualization:
Before sort: [2,6] [1,3] [15,18] [8,10]
After sort: [1,3] [2,6] [8,10] [15,18]
Merge process:
┌─────────────────────────────────────┐
│ current = [1,3] │
├─────────────────────────────────────┤
│ Compare with [2,6]: │
│ 3 ≥ 2 → Overlap! │
│ current = [1, max(3,6)] = [1,6] │
├─────────────────────────────────────┤
│ Compare with [8,10]: │
│ 6 < 8 → No overlap │
│ Save [1,6], current = [8,10] │
├─────────────────────────────────────┤
│ Compare with [15,18]: │
│ 10 < 15 → No overlap │
│ Save [8,10], current = [15,18] │
├─────────────────────────────────────┤
│ End of array, save [15,18] │
└─────────────────────────────────────┘
Result: [[1,6], [8,10], [15,18]]
Let's Continue Our Fresher's Algorithm in the next part here
Top comments (0)