Day 12 – Spiral Matrix, Subarray Sum = K, Pascal’s Triangle, Majority Elements (> n/3), and 3Sum
Published
•5 min readWorked through classic matrix traversal, subarray prefix sums, combinatorics, and frequency-based problems using hashing and two-pointer techniques.
LeetCode 54 – Spiral Matrix
Traverse matrix layer by layer in spiral order.
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
for (int i = left; i <= right; i++) res.push_back(matrix[top][i]);
top++;
for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);
right--;
if (top <= bottom)
for (int i = right; i >= left; i--) res.push_back(matrix[bottom][i]);
bottom--;
if (left <= right)
for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);
left++;
}
return res;
}
// TC: O(n * m)
// SC: O(1) (excluding result vector)
LeetCode 560 – Subarray Sum Equals K
1. Brute Force (All subarrays)
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for (int i = 0; i < nums.size(); i++) {
int sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}
// TC: O(n²)
// SC: O(1)
2. Better – Prefix Sum Array
int subarraySum(vector<int>& nums, int k) {
vector<int> prefix(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++)
prefix[i + 1] = prefix[i] + nums[i];
int count = 0;
for (int i = 0; i < prefix.size(); i++)
for (int j = i + 1; j < prefix.size(); j++)
if (prefix[j] - prefix[i] == k) count++;
return count;
}
// TC: O(n²)
// SC: O(n)
3. Optimal – Prefix Sum with Hash Map
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1; // empty prefix
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
if (mp.count(sum - k)) count += mp[sum - k];
mp[sum]++;
}
return count;
}
// TC: O(n)
// SC: O(n)
LeetCode 118 – Pascal’s Triangle
1. Print Full Triangle (All Rows)
vector<vector<int>> generate(int numRows) {
vector<vector<int>> triangle(numRows);
for (int i = 0; i < numRows; i++) {
triangle[i].resize(i + 1, 1);
for (int j = 1; j < i; j++)
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
return triangle;
}
// TC: O(n²)
// SC: O(n²)
2. Print Specific Row Only
vector<int> getRow(int rowIndex) {
vector<int> row = {1};
long long val = 1;
for (int i = 1; i <= rowIndex; i++) {
val = val * (rowIndex - i + 1) / i;
row.push_back(val);
}
return row;
}
// TC: O(n)
// SC: O(n)
3. Print Specific Element (nCr)
int nCr(int n, int r) {
long long res = 1;
for (int i = 0; i < r; i++) {
res *= (n - i);
res /= (i + 1);
}
return (int)res;
}
// TC: O(r)
// SC: O(1)
LeetCode 229 – Majority Element (> n/3)
Key Insight: At most 2 elements can have count > n/3.
1. Brute Force – Count all
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
for (int i = 0; i < nums.size(); i++) {
int count = 0;
for (int j = 0; j < nums.size(); j++)
if (nums[j] == nums[i]) count++;
if (count > nums.size() / 3 && find(ans.begin(), ans.end(), nums[i]) == ans.end())
ans.push_back(nums[i]);
}
return ans;
}
// TC: O(n²)
// SC: O(1)
2. Better – Hash Map
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> mp;
vector<int> res;
for (int n : nums) mp[n]++;
for (auto [k, v] : mp)
if (v > nums.size() / 3) res.push_back(k);
return res;
}
// TC: O(n)
// SC: O(n)
3. Optimal – Extended Boyer-Moore Voting
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
int cnt1 = 0, cnt2 = 0, ele1 = INT_MIN, ele2 = INT_MIN;
for (int num : nums) {
if (cnt1 == 0 && num != ele2) ele1 = num, cnt1 = 1;
else if (cnt2 == 0 && num != ele1) ele2 = num, cnt2 = 1;
else if (num == ele1) cnt1++;
else if (num == ele2) cnt2++;
else cnt1--, cnt2--;
}
cnt1 = cnt2 = 0;
for (int num : nums) {
if (num == ele1) cnt1++;
else if (num == ele2) cnt2++;
}
vector<int> res;
if (cnt1 > n / 3) res.push_back(ele1);
if (cnt2 > n / 3) res.push_back(ele2);
return res;
}
// TC: O(n)
// SC: O(1)
➕ LeetCode 15 – 3Sum
1. Brute Force – 3 Loops + Set
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> st;
int n = nums.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (nums[i] + nums[j] + nums[k] == 0) {
vector<int> temp = {nums[i], nums[j], nums[k]};
sort(temp.begin(), temp.end());
st.insert(temp);
}
return vector<vector<int>>(st.begin(), st.end());
// TC: O(n³ log 3) ≈ O(n³), SC: O(no. of triplets)
2. Better – HashSet + Fix One Element
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> st;
int n = nums.size();
for (int i = 0; i < n; i++) {
set<int> hash;
for (int j = i + 1; j < n; j++) {
int third = - (nums[i] + nums[j]);
if (hash.count(third)) {
vector<int> triplet = {nums[i], nums[j], third};
sort(triplet.begin(), triplet.end());
st.insert(triplet);
}
hash.insert(nums[j]);
}
}
return vector<vector<int>>(st.begin(), st.end());
// TC: O(n² log 3) ≈ O(n²), SC: O(n) + output
3. Optimal – Sort + Two Pointer
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int low = i + 1, high = n - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if (sum < 0) low++;
else if (sum > 0) high--;
else {
res.push_back({nums[i], nums[low], nums[high]});
while (low < high && nums[low] == nums[low + 1]) low++;
while (low < high && nums[high] == nums[high - 1]) high--;
low++; high--;
}
}
}
return res;
// TC: O(n²), SC: O(1) (excluding output)