Week: 9th Sept - 15th Sept ‘26#
4038. Count Integers Appearing in a Single Block#
My first approach was to basically save all frequencies of each number. Then try to find the starting and ending indexes of any contiguous block, and if the gap between starting and ending of that block isn’t same as the frequencies of said digit inside the block, it’s invalid. If not, it’s valid. I wrote:
class Solution {
public:
int countSpecialIntegers(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> freq;
int count = 0;
if (n==1) return 1;
for (int x : nums){
freq[x]++;
}
int start = -1;
int end = -1;
for (int i = 0; i < n; i++){
if (i>0 && i<n-1){
if (nums[i-1] != nums[i] && nums[i+1] == nums[i]){
start = i;
end = i;
}
if (nums[i-1] == nums[i] && nums[i+1] != nums[i]){
end = i;
}
if (nums[i-1] != nums[i] && nums[i+1] != nums[i]){
start = i;
end = i;
}
}
if (i==0){
if (nums[i+1] == nums[i]) start = i;
else {
start = i;
end = i;
}
}
if (i == n-1){
if (nums[i-1] == nums[i]) end = i;
else {
start = i;
end = i;
}
}
if (end >= start && freq[nums[i]] == (end - start + 1)) count++;
}
return count;
}
};which I am 100% sure I overcomplicated. I’m also sure the small constraints on this would make it easier, but overall, this is the best I could do for now.
But I do think I can make an array of size 100 and store true false values there as another approach?
Yes! I can store the count of starts of each continuous block and if some number has more than one start then it won’t be counted. Count all the ones hehe.
class Solution {
public:
int countSpecialIntegers(vector<int>& nums) {
int n = nums.size();
vector<int> runs(101, 0);
for (int i=0; i < n; i++){
if (i == 0 || nums[i] != nums[i-1]) runs[nums[i]]++;
}
int count = 0;
for (int x : runs){
if (x == 1) count++;
}
return count;
}
};3870. Count Commas in Range#
Simplest code ever. Saved by the constraint of max n being 10^5.
class Solution {
public:
int countCommas(int n) {
if (n < 1000) return 0;
else return (n - 999);
}
};3871. Count Commas in Range II#
Not so simple man. So many numbers. But we made it. I counted each comma in each possible range and added them.
class Solution {
public:
long long countCommas(long long n) {
long long sum = 0;
if (n < 1000) return 0;
if (n >= 1e3 && n < 1e6) sum = 1*(n-(1e3-1));
if (n >= 1e6 && n < 1e9) sum = 1*(1e6-1e3)+2*(n-(1e6-1));
if (n >= 1e9 && n < 1e12) sum = 1*(1e6-1e3)+2*(1e9-1e6)+3*(n-(1e9-1));
if (n >= 1e12 && n < 1e15) sum = 1*(1e6-1e3)+2*(1e9-1e6)+3*(1e12-1e9)+4*(n-(1e12-1));
if (n == 1e15) sum = 1*(1e6-1e3)+2*(1e9-1e6)+3*(1e12-1e9)+4*(1e15-1e12)+5*(n-(1e15-1));
return sum;
}
};It can be improved clearly because writing codes like this takes too long, assuming I’m in a competition.
This improvement lies in changing the approach. Instead of asking “How many commas does this number have” ask “how many numbers have k commas?” Every number after 1,000 has 1 comma, every number after 1,000,000 has one more comma.
We can sum the number of commas per range. If n exists, then all numbers between 1000 and n have 1 comma, then all numbers between 1,000,000 and n have another comma and so on.
The simpler approach:
class Solution {
public:
long long countCommas(long long n) {
long long sum = 0;
for (long long p = 1000; p < n; p *= 1000){
sum += n - p + 1; //total numbers between p and n, each containing one extra comma per loop
}
return sum;
}
};4048. Count Values With Equally Spaced Occurrences I#
My solution using hashmaps:
class Solution {
public:
int countSpecialIntegers(vector<int>& nums) {
unordered_map<int, vector<int>> mapp;
for (int i = 0; i < nums.size(); i++){
mapp[nums[i]].push_back(i);
}
int total = 0;
for (auto [key, value] : mapp){
if (value.size() == 3){
if (value[0] < value[1] && value[1] < value[2]){
if (value[1] - value[0] == value[2] - value[1]){
total++;
}
}
}
}
return total;
}
};Basically store indexes and check the condition after. If matched, et voila.
4049. Count Values With Equally Spaced Occurrences II#
My solution, took my a while due to me reading the question wrong.
class Solution {
public:
int countSpecialIntegers(vector<int>& nums) {
int total = 0;
unordered_map<int, vector<int>> mapp;
for (int i = 0; i < nums.size(); i++){
mapp[nums[i]].push_back(i);
}
for (auto [key, value] : mapp){
if (value.size() >= 3){
int low = 0; int mid = 1; int high=2;
while (high < value.size()){
if (value[low] < value[mid] && value[mid] < value[high]){
if (value[mid] - value[low] == value[high] - value[mid]){
low++; mid++; high++;
}
else {
break;
}
}
}
if (low == value.size()-2 &&
mid == value.size()-1 &&
high== value.size()) total++;
}
}
return total;
}
};Same as before, except we have to check for each pair. O(n) time complexity since we visit each element (index) only once.
4052. Cyclically Shift Rows and Columns#
class Solution {
public:
vector<vector<int>> cyclicShift(int n, vector<vector<int>>& grid, vector<int>& rowShift, vector<int>& colShift) {
for (int r = 0; r < rowShift.size(); r++){
vector<int> copy = grid[r];
for (int i = 0; i < n; i++){
grid[r][(i - rowShift[r] + n) % n] = copy[i];
}
}
for (int c = 0; c < colShift.size(); c++){
vector<int> copy;
for (int j=0; j<n; j++){
copy.push_back(grid[j][c]);
}
for (int i = 0; i < n; i++){
grid[(i - colShift[c] + n) % n][c] = copy[i];
}
}
return grid;
}
};Took my an hour because I was doing this without any sleep, and kept messing over this line 16. grid[(i - colShift[c] + n) % n][c] = copy[i]; where I had written 16. grid[i][c] = copy[(i - colShift[c] + n) % n]; instead.
O(n2) solution sadly but the constraints were forgiving so whatever. Go to each rowShift row, go to that row in the grid, calculate the new values from a copy of that row. Do the same for the columns (but copy the columns first through a loop as you can’t directly equate like in rows).
836. Rectangle Overlap#
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
int x1 = rec1[0];
int y1 = rec1[1];
int x2 = rec1[2];
int y2 = rec1[3];
int x1_ = rec2[0];
int y1_ = rec2[1];
int x2_ = rec2[2];
int y2_ = rec2[3];
if (((y1 < y1_ && y1_ < y2) || (y1 < y2_ && y2_ < y2)) && ((x1_ < x1 && x1 < x2_) || (x1_ < x2 && x2 < x2_))){
return true;
}
if (((y1_ < y1 && y1 < y2_) || (y1_ < y2 && y2 < y2_)) && ((x1 < x1_ && x1_ < x2) || (x1 < x2_ && x2_ < x2))){
return true;
}
if (
(((x1_ <= x1 && x1 <= x2_) && (x1_ <= x2 && x2 <= x2_)) && ((y1_ <= y1 && y1 <= y2_) && (y1_ <= y2 && y2 <= y2_))) ||
(((x1 <= x1_ && x1_ <= x2) && (x1 <= x2_ && x2_ <= x2)) && ((y1 <= y1_ && y1_ <= y2) && (y1 <= y2_ && y2_ <= y2)))
) return true;
return false;
}
};Did all calculations of what possible overlap can occur based on coordinates of the diagonals. F*uckass.
Better solution:
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
return rec1[0] < rec2[2] &&
rec1[2] > rec2[0] &&
rec1[1] < rec2[3] &&
rec1[3] > rec2[1];
}
};Just calculate if the edges overlap. If they do, we have overlapping area.
21. Merge Two Sorted Lists#
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr && list2 != nullptr) return list2;
if (list2 == nullptr && list1 != nullptr) return list1;
if (list2 == nullptr && list1 == nullptr) return nullptr;
ListNode* output = nullptr;
if (list1->val <= list2->val){
output = list1;
list1 = list1->next;
} else {
output = list2;
list2 = list2->next;
}
ListNode* head = output;
while (list1 != nullptr && list2 !=nullptr){
if (list1->val <= list2->val){
output->next = list1;
list1 = list1->next;
}
else if (list1->val > list2->val){
output->next = list2;
list2 = list2->next;
}
output = output->next;
}
while (list1 != nullptr && list2 == nullptr){
output->next = list1;
list1 = list1->next;
output = output->next;
}
while (list1 == nullptr && list2 != nullptr){
output->next = list2;
list2 = list2->next;
output = output->next;
}
return head;
}
};F*cking hell writing this was stupid. Confusion over linked list nodes, and which pointer to advance etc. The intuition is simple. Let output store the first node which is lesser from either list. Then as we keep going, keep attaching pointers to the output list as you find the lesser node from the lists. If you reach the end of one list, attach the other to the output. When you reach the end of both, return the head node.