Issue 01

This site is a running log of things I learn and the projects I build. The most important property it has is that publishing is frictionless: writing a new post is exactly as much work as creating a Markdown file and pushing to git. No CMS, no dashboard, no database.

The stack#

It’s built with Astro as a fully static site. Every TIL and every post is a Markdown file with a little frontmatter block at the top — a title, a date, some tags. Astro reads those files at build time, validates the frontmatter against a schema, and turns each one into a page. The output is plain HTML and CSS with essentially no client-side JavaScript, so pages load instantly and there’s nothing to break.

There are two kinds of writing here:

• TILs (“Today I Learned”), short, dated, tagged notes. This is the heart of the site and where most of the activity is.
• Posts, longer writeups and essays, like this one.

Why no JavaScript framework#

Because the content is the product. A personal site that’s mostly text doesn’t need a rendering framework shipped to the browser; it needs good typography, a readable column width, and fast loads. Keeping the build static means the whole site is a folder of HTML files that any host can serve, and there’s no runtime to patch or attack.

Following along#

Everything is available as a feed. There’s a combined feed of TILs and posts, and if you only want one or the other, each has its own. Feeds carry the full text, so you can read without ever visiting the site that’s the point of them.

If you want to see how the sausage is made, the source is on GitHub.

Kicking off a link blog here, the way Simon Willison does it: short posts that point at something worth your time with a line on why. Less pressure than an essay, and over a year it becomes the most useful thing on the site. This is the first one.

Introduction#

• Array stores data in continuous or contiguous memory.
• All accessible in O(1) time, because it directly reaches address of elements inside by simple arithmetic, BECAUSE they are all stored together.
• But, there’s problems with this contiguous memory is that when there’s no space for the next element you must copy the elements to a new location, wasting time.
• That’s why we use linked lists because it stores it’s data in random places of the memory and each are connected.

Linked Lists#

• Stores data in Nodes that are spread out in memory but all nodes are storing address of the next node in the list.
• Traversal time complexity: O(n)
• Insertion time complexity: O(n)

Arrays vs linkedlists#

a) Cost of Accessing an element#

• Array needs constant time O(1) because simple arithmetic leads to the next element.
• Address of i th element = Base_address + i * Size_of_data_type
• Linked List needs O(n) where is n is number of elements in the list.

B) Memory Requirement#

• Array has a fixed size, so partially filled array takes as much space as it was full.

• So there’s a lot of unused space in memory.

• Sometimes, memory may not be available all the time since contiguous memory so it requires copying of data.

• Linked List requires extra memory for pointer variables. They are 4 bytes each (in 32bit system). But 8 bytes in 64bit system.

• But it does not leave unused memory.

• It’s usually better than array when the datatype being stored has higher size. But depends on the case on which performs better.

• Nodes being stored at random places in memory.

C) Cost of insertion#

1. In the beginning
   • Arrays have to shift all elements by one and then insert the value at starting. So O(n)
   • Linked List disconnects head node and reattaches new node in the beginning. So O(1)
2. In the end
   • Arrays: Just insert element at the new free location, or copy into new array if it is full. So O(1) or O(n)
   • Linked List needs to traverse until the end then attach new node. So O(n)
3. At i-th location (average case)
   • Arrays: Shift some elements forward. So O(n)
   • Linked list: Traverse i elements, so O(n)

Implementation in both C and C++#

Making a node

typedef struct Node{
	int data;
	struct Node* next;
} Node;

struct Node{
	int data;
	Node* next;
};

Initializing Linked List

Node* A; //initialising empty LL
A = NULL; //Setting it as Null initially
Node* temp = (Node*) malloc(sizeof(struct Node)) //typecasting required, creating a new temporary node
(*temp).data = 2; //Filling data in node
(*temp).next = NULL; //Attaching it to null address
A = temp; //Setting A as temp node

Node* A;
A = NULL;
Node* temp = new Node();
temp->data = 2;           // -> is basically short form of the deferencing (*) and accessing structure with .
temp->next = NULL;
A = temp;

Node* temp1 = A;
while (temp->next != NULL){
	temp1 - temp1 -> next;
}

temp = new Node();
temp->data = 4;
temp->next = NULL;
temp1->next = temp;

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
	int data;
	struct Node* next;
} Node;

void Insert(Node** pointerToHead, int x);
void Print(Node* head);

int main(){
	struct Node* head = NULL;
	int n,x;
	printf("Enter number of nodes: ")
	scanf("%d", &n);
	for (int i=0; i < n; i++){
		printf("Enter a number: ");
		scanf("%d", &x);
		Insert(&head, x);
		Print(head);
	}
	printf("\n");
}

void Insert(Node** pointerToHead, int x){
	Node* temp = (Node*) malloc(sizeof(struct Node));
	temp->data = x;
	temp->next = *pointerToHead;
	*pointerToHead = temp;
}

void Print(Node* head){
	while (head != NULL){
		printf("%d ",head->data);
		head = head->next;
	}
	printf("\n");
}

Notes:

• Node** is a pointer to pointer. Dereferencing it gives us the pointer to a Node. Then we can use -> to grab its data and next
• We used pointer-to-pointer so that we can modify what is at the address of the memory. If we used pointer directly, that would not work because this new argument inside Insert would be a COPY of the pointer and not the one we want to modify.
• Insert function handles both empty and non-empty linked list as if it is empty then head is null which the new temp node takes anyways.
• For C++ we can use classes and the new function (Node* temp = new Node();) for easy.
• This code still doesn’t free up memory.

Arrays and Hashing#

1. Contains duplicate#

class Solution {
public:
    bool hasDuplicate(vector<int>& nums) {
        set<int> myset;
        for (int i=0; i < nums.size(); i++){
            int temp = myset.size();
            myset.insert(nums[i]);
            if (temp == myset.size()) return true;
        }
        return false;
    }
};

• Time Complexity: O(nlogn) because I used set, which uses binary search trees and is ordered. It’s insert operation is O(logn) so doing it n times = O(nlogn)
• Space Complexity: O(n), size of set.

What can be made better?#

• As set is basically BST, it’s tree operations take logn time. Instead use a hash table (unordered_set) which is basically a bucket system, and it’s operations are in average case O(1). Close because the worst case is O(n) if all the elements collide into ONE bucket.

New things#

• Insert: is an API, it returns a pair<iterator, bool> where iterator is basically a pointer to either the new element added (in which case bool is true) or the already existing element that didn’t get inserted again (bool being false). Thus, without checking for size in each loop, we could just check if the pair.second value was false.
• count and contains can become alternatives for the if condition, checking if the set contained the element already. But insert.second is much cleaner.
• Count: .count(number) gives how many times number appeared in the container. For sets and unordered_sets it is either 0 or 1 because each element is unique. So we could use this too.
• Contains (for newer C++20): .contains(number) is a boolean function that returns true if an element exists in the container.
• So instead of “did size increase?” we could have “is this element already in the set?” If both output 0 (the element was not there) then insert the element and continue. If both output 1 (the element is already there!) break and return, since this is a duplicate.
• So this would eventually lead us to O(n) instead of O(nlogn)!

Some errors that went unnoticed#

• nums.size() outputs an unsigned integer size_t (a non-negative number) but in the for loop, using int i=0 makes i a signed integer. Now usually this is fine. C++ converts i to unsigned integer during the comparison (i < nums.size()) and it doesn’t break.
• Yet it WILL break in the case where nums.size() = 0 and we compute nums.size() - 1. The output would not be -1 but some huge number.
• Fix? Use size_t i OR write loops using elements themselves (for (int x : nums)).

Extras#

• size_t is a type, just like int, float or bool. The standard library uses it for sizes and indices, which are all non-negative numbers. As .size() returns size_t, it’s just better to compare it to an i which is size_t and not int.
• auto is the lazy-guy’s alternative to all. At compile time (when the code is converted to assembly/machine language) auto is decided by the type of what is on the right side of it.
• So if we wanted the pair output of set.insert() we’d have to create pair<unordered_set<int>::iterator, bool> result = set.insert(number); but auto result = set.insert(number) is easy to write.
• Each STL container has its own iterator, and they’re different because of different traversal mechanics used in each container (like set is BST, unordered_set is buckets, vector is contiguous). Each iterator is accessed by container<type>::iterator and follows the same three buttons. *it outputs object at location, ++it takes to the next location, and it != cont.end() asks if we are at the end or not.
• The number -1 for unsigned integer would be 2^64 - 1 (or 2^32 - 1 for 32 bit systems).

class Solution {
public:
    bool hasDuplicate(vector<int>& nums) {
        unordered_set<int> myset;
        for (size_t i=0; i < nums.size(); i++){
            auto result = myset.insert(nums[i]);
            if (result.second == false) return true;
        }
        return false;
    }
};

class Solution {
public:
    bool hasDuplicate(vector<int>& nums) {
        unordered_set<int> myset;
        for (size_t i=0; i < nums.size(); i++){
            if (myset.count(nums[i]) == 1) return true;
            myset.insert(nums[i]);
        }
        return false;
    }
};

2. Valid Anagram#

class Solution {
public:
    bool isAnagram(string s, string t) {
        multiset<char> s_set;
        multiset<char> t_set;
        for (char a : s){
            s_set.insert(a);
        }
        for (char b : t){
            t_set.insert(b);
        }
        if (s_set == t_set) return true;
        return false;
    }
};

• Time Complexity: O((n+m)log(n+m)) Space Complexity: O(n+m)
• Can be improved by using two other solutions, each using the same concept:
  • Using a hash map, which stores counts of each char
  • As characters are only 26 in number, an array of 26 size can store frequency of each character and index can be easily calculated using the trick c - 'a where c is a character.
• The concept: As you go along s increment counts of each character, and as you go along t decrement counts of each character. If both were anagrams, the hashmap or array would all be containing zeroes. If any is non-zero, then both strings had different number of characters or different characters themselves.

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> freq;
        for (char a : s){
            freq[a]++;
        }
        for (char b : t){
            freq[b]--;
        }
        for (const auto& x : freq){
            if (x.second != 0) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        int freq[26] = {0};
        for (char a : s){
            freq[a - 'a']++;
        }
        for (char b : t){
            freq[b - 'a']--;
        }
        for (int x : freq){
            if (x != 0) return false;
        }
        return true;
    }
};

New#

• auto vs auto&: auto& is faster because it doesn’t copy the value. It refers to the original value itself. So any modifications to it will modify the original.
• An initial guard of checking both string length would save some time and allow me to write a common for loop for both increments and decrements.
• const is used to tell the compiler that this variable will not be modified. Even if you try to, it won’t work.
• const auto& seems counter intuitive (why would I want to auto& for modifying but const to keep it same) but in reality you get best of both worlds here, as auto& saves time but const stops any accidental modifications to the original value.
• But in all seriousness, these auto& stuff doesn’t really matter for small data types like int, char, bool but does in strings/vectors or bigger data structures. So auto is fine. Both are same speed for the small data types.

3. Two sum#

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++){
            hash[nums[i]] = i;
        }
        for (int i = 0; i < n; i++){
            if (hash.find(target - nums[i]) != hash.end() && i != hash[target - nums[i]]) return {min(i, hash[target - nums[i]]), max(i, hash[target - nums[i]])};
        }
        return {};
    }
};

Problems I faced#

• Tried a two pointer approach first, incrementing and decrementing one by one but it had a major flaw of ignoring values that aren’t symmetrically placed in the array
• Then I knew I had to use the O(1) finding ability of hashmaps.
• Got confused over unordered_set and unordered_map
• Had to look up how find() works and how if it doesn’t work I have to use hash.end()
• Problems saving the index, at first tried hash[nums[i]]+=i assuming it gets created with 0 first then I could add i to it, but later realized I have to literally equate it to i.
• Then only some syntax errors while writing the return value.
• Wanted to use auto& x : nums but needed index information so had to resort to i. find() gave out an iterator (pointer) which is not what I needed. I could dereference it and find the key (the number) using .first and its index (value) using .second
• Then faced the same index error which I fixed with a simple condition.

What can be made better#

• Even though this is O(n) it required two passes (it completed in 2n time) it was still possible to do it in one pass. n and 2n don’t matter to Big-O, but one passes achieves the same thing in half the number of operations.
• The possibility being, before you add the current element, check whether its complement is already in the array. If it is, return. If it’s not, add the element in hash map then go to next element.
• This also solves the same-index error as well, because since we are creating the hash map as we go, same index values don’t exist. The moment we find a solution we return.
• It ALSO solves the fact that we have to return the lower index first. Since the current element is the latest one, the complement would already be before it. So its index is automatically lower.
• Why hash.find(x)->second is better? Because if I used hash[x] it would have created a value in the hash map, being 0. This creation is useless and wastes memory. hash.find(x)->second doesn’t create anything.
• I could replace hash.find(x) != hash.end() with hash.contains(x) which is much cleaner but only available in C++20.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        int n = nums.size();
        for (int i = 0; i < n; i++){
            int x = target - nums[i];
            if (hash.find(x) != hash.end()) return {hash.find(x)->second, i};
            hash[nums[i]] = i;
        }
        return {};
    }
};

4. Group Anagrams#

class Solution {
public:
    bool testForAnagram(string s1, string s2){
        if (s1.size() != s2.size()) return false;
        unordered_map<char, int> freq;
        for (int i=0; i<s1.size();i++){
            freq[s1[i]]++;
            freq[s2[i]]--;
        }
        for (auto& x : freq){
            if (x.second != 0) return false;
        }
        return true;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<vector<string>> output;
        for (int i = 0; i < n; i++){
            output.push_back({strs[i]});
        }
        for (int i = 0; i < output.size(); i++){
            for (int j = 0; j < output.size(); j++){
                if (i != j && testForAnagram(output[i][0], output[j][0])){
                    output[i].insert(output[i].end(), output[j].begin(), output[j].end());
                    output.erase(output.begin() + j);
                    j--;
                }
            }
        }
        for (int i = 0; i < output.size(); i++){
            if(output[i].size() == 0) {
                output[i] = output.back();
                output.pop_back();
            }
        }
        return output;
    }
};

Complexity#

• Time: O(n2.k)
• Space: O(n.k)

Problems I faced#

• Well at first the problem was hard enough. But I had a feeling I’d be able to at least complete it.
• At first I got the normal anagram function down, the one we did before, in a separate function of its own which I can call anytime. I knew there would be many comparisons this time, so it would be easier to write a function beforehand to stop things from getting messy.
• Then at first I was going for testing each pair of strings, which would be O(n2) but before I wrote the for loop I thought combining multiple strings into vectors would be tough. So I thought of a different approach.
• I knew I had to create vectors, so I made the trivial solution of no anagrams at all. This was a vector of vectors each with one string. Next I’d start combining the elements of vectors having the their first elements as anagrams. If the vector had a higher size, the first element would confirm that the other elements in it were anagrams themselves.
• So combining, I had to look up multiple syntaxes. How to insert elements, how to erase elements, how to delete without fucking up everything etc.
• Combined using a method where you grab the second vector and copying all elements inside the first vector. Its syntax was weird (the insert one). Then deleted the second vector. (After seeing a test case fail with heap exceed I realized I had to reduce j too because of the deletion).
• I also had a problem of selecting which vectors to combine. At first I had j=i+1 as the starting condition, but this soon made it such that I’d forget to check elements before i. So I just added a guard of i != j alongside the anagram function and made j start from 0 every time.
• And? Et voila!
• Clearly this wasn’t the best solution lmfao. But I’m happy I solved it.

The better way#

• The better way is out of this world. It utilizes the concept that all anagrams, once sorted, are the same. Which means, each anagram has a unique ‘key’.
• And guess what? We can have buckets of all anagrams under that unique key, always accessible in O(1) time through a hash map. Each anagram can go into its unique key bucket, and finally, we can output these buckets. Mind = blown.
• Let’s try it.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> u_keys;
        for (const auto& s : strs){
            string key = s;
            sort(key.begin(), key.end());
            u_keys[key].push_back(s);
        }
        vector<vector<string>> output;
        for (const auto& [key, group] : u_keys){
            output.push_back(group);
        }
        return output;
    }   
};

• Time Complexity: O(n.k.log k) and Space: O(n.k)
• A faster solution exists O(n.k), where I don’t have to sort. I can create unique keys myself using arrays.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> u_keys;
        for (const auto& s : strs){
            int freq[26] = {0};
            for (char c : s){
	            freq[c - 'a']++;
            }
            string key = "";
            for (int i=0; i < 26; i++){
	            key += '#';
	            key += to_string(freq[i]);
            }
            u_keys[key].push_back(s);
        }
        vector<vector<string>> output;
        for (const auto& [key, group] : u_keys){
            output.push_back(group);
        }
        return output;
    }   
};  

• Because char is an integer type, it remembers its ascii value. Meaning if char + int happens, the output would not be two appended chars but an integer number. When added to the key (a string) it would add as the ascii equivalent of that integer, so the final key would actually be weird characters. This is bad because this can confuse the key in cases like 11#2 and 1#12. Hence why we need a separator #.

5. Top K frequent elements#

• It seems I’m at my mind’s limit, so I’m going to take a break now. Here’s my brute force solution:

  class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int x : nums){
            freq[x]++;
        }
        vector<int> output;
        for (int i=0; i<k; i++){
            int maxi=0;
            for (const auto& [key, value] : freq){
                maxi = max(maxi, value);
            }
            for (const auto& [key, value] : freq){
                if (value == maxi){
                    output.push_back(key);
                    freq[key]=0;
                    break;
                }
            }
        }
        return output;
    }
};

• Time Complexity: O(k.n)
• Space Complexity: O(n)

Problems I faced#

• At first I misundertood the question and solved for ‘return whatever number had atleast k frequency’ and thought why tf was this a medium problem.
• Then I realised it was to return the most frequent numbers, and to return the best k among.
• I thought this was simple, but then I found out that you can’t really order a hash map through it’s values. I’d have to find it manually.
• So I found it manually. Looped k times for the requirement, found the maximum value, then located which key had that maximum value, then inserted it into my output and reset its frequency to 0. Of course I had to break this because that loop needed only one maximum not all of them.

What can be done better#

• Using bucket sort, we could store the numbers in buckets of their frequencies. Basically, take a vector where index = frequency and store the numbers with frequency there in a vector.
• So then each number at say ith index appears i times.
• Then we can grab the elements in the descending order, as most frequent ones are at the end of the frequency vector. The moment we have k numbers, we return the solution.
• This solution has O(n) and not O(n2) because even though there is a nested loop, the effective work done is ONCE per number. And at most that can be n.

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> freq(n+1);
        unordered_map<int, int> mapp;
        for (int x : nums){
            mapp[x]++; //store frequencies in hashmap
        }
        for (const auto& [key, value] : mapp){
            freq[value].push_back(key); //create a vector at said frequency's location and store the number there
        }
        vector<int> output;
        for (int i = n; i > 0; i--){
            if (freq[i].size() != 0){
                for (int j : freq[i]){ //find the numbers and push to output
                    if (output.size()!=k) output.push_back(j);
                    else break;
                }
            }
        }
        return output;
    }
};

6. Encode and Decode strings#

class Solution {
public:
    char c = 'a' - 1;
    string encode(vector<string>& strs) {
        string s = ""; 
        s += c;
        for (const auto& x : strs){
            s += x;
            s += c;
        }
        return s;
    }

    vector<string> decode(string s) {
        vector<string> output;
        if (s == to_string(c)) {
            output.push_back(s);
            return output;
        }
        string temp = "";
        for (int i = 0; i < s.size(); i++){
            if (s[i] != c){
                temp += s[i];
            }
            else {
                output.push_back(temp);
                temp = "";
            }
        }
        output.erase(output.begin());
        return output;
    }
};

Problems:#

• I knew for a fact that this code was broken. With multiple test cases failing and fixing the test cases only I wasn’t thinking in terms of fixes but ‘just pass’.
• A fatal flaw in the code is the handling of empty vectors. The encoded string is the delimiter c, and when decoding, we finally pop the first element. This was accidentally working because when an empty string "" was passed it needed to be in the output. But not always.
• In any case, this problem only works on ASCII characters because I used a delimiter not in the ascii range.
• The better solution was to use lengths.

What can be done better:#

• I can encode a word using the lengths of the string, any character as a delimiter, and the word itself.
• Decoding is easy now because I have to look for a number (use string math to convert it to an integer), stop looking when I see a delimiter, then construct the word after iterating through the string for length loops.
• Let’s try it.

class Solution {
public:

    string encode(vector<string>& strs) {
        if (strs.empty()) return "";
        string s;
        for (const auto& x : strs){
            s += to_string(x.size());
            s += '#';
            s += x;
        }
        return s;
    }

    vector<string> decode(string s) {
        if (s == "") return {};
        vector<string> output;     
        int i=0;
        while (i<s.size()){
            string len_str="";
            int length = 0;
            while (s[i] != '#'){
                len_str += s[i];
                i++;
            }
            length = stoi(len_str);
            string temp = "";
            i++;
            for (int j=0; j<length; j++){
                temp += s[i];
                i++;
            }
            output.push_back(temp);
        }
        return output;
    }
};

• There’s definitely a cleaner way to write this.
• We can use two different methods, the latter being more readable while the former is cleaner.
• We could use stoi function’s property of automatically finding numbers and also reporting how many characters it read. stoi(substr(i), &n) means: In the substring from index i till the end, grab the first few numbers and when you find a non-numeric character, stop and report back how many characters you consumed inside n (which MUST be size_t and not int).
• OR we could simply use find('#', i) which means return the index where you locate '#' after i. So between i and returned value say j, is the number, which we can convert to an int using stoi(substr(i, j-i)). substr(pos, count) is the syntax.
• Here’s decode in both ways:

vector<string> decode(string s){
	    if (s=="") return {};
	    vector<string> output;     
        size_t i=0;
        while (i<s.size()){
            size_t n;
            int length = stoi(s.substr(i), &n);
            i+=n+1;
            output.push_back(s.substr(i, length));
            i+=length;
        }
        return output;
    }

vector<string> decode(string s){
	    if (s=="") return {};
	    vector<string> output;     
        size_t i=0;
        while (i<s.size()){
            size_t j = s.find('#', i);
            int length = stoi(s.substr(i, j-i));
            i = j+1;
            output.push_back(s.substr(i, length));
            i+=length;
        }
        return output;
    }

7. Products of Array except self#

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int product = 1;
        int product_wo_zero = 1;
        int zero_counter = 0;
        for (size_t i = 0; i < nums.size(); i++){
            if (nums[i]==0){
                zero_counter++;
            }
            if (zero_counter < 2) {
                if (nums[i] == 0) product *= nums[i];
                else {
                    product *= nums[i];
                    product_wo_zero *= nums[i];
                }
            }
            else {
                vector<int> meow(nums.size(), 0);
                return meow;
            }
        }
        for (int& x : nums){
            if (zero_counter == 0){
                x = product/x;
            }
            else if (zero_counter == 1){
                if (x != 0) x=0;
                else x = product_wo_zero;
            }
        }
        return nums;
    }
};

My thinking#

• I knew the naive solution to be grab one element, scroll through the array, and put the values in a different vector, then return it. This was clearly O(n2), so I didn’t go for it.
• Unfortunately, before I could think, the question had a follow up right in the question. “Can you solve it in O(n) without using division approach” and it clicked to me instantly that I could grab the entire product and divide it to each element. So in two passes, one for grabbing the product and another for updating the array, this would be solved.
• Boom, wrote that, then realised that zeroes are a bitch. Not just zero making everything zero, if there was only one zero, it would make every other element zero except itself. So I had to calculate a product_without_zeroes and a product (with zeroes) seperately, then according to the current num I’d replace it with the appropriate value.
• For 2 zeroes and more, the solution is trivial. All zeroes.

What can be made better#

• Storing prefix products except current element at the current element, and similarly for postfix products, we can multiply those numbers to get the accurate answer every time.
• Each prefix[i] holds the product of everything before i, each postfix[i] the product of everything after i, so prefix[i] * postfix[i] is the product of all elements except i.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> prefix(nums.size(), 1);
        vector<int> postfix(nums.size(), 1);
        for (size_t i = 1; i < nums.size(); i++){
            prefix[i] = nums[i-1]*prefix[i-1];
        }
        for (int j = nums.size()-2; j >= 0; j--){
            postfix[j] = postfix[j+1]*nums[j+1];
        }
        for (size_t i = 0; i < nums.size(); i++){
            nums[i] = prefix[i]*postfix[i];
        }
        return nums;
    }
};

• This can also be shortened into only two passes, without any extra space complexity. We basically store the postfix in a variable and update that in each pass over output, which already contains the prefix products after the first for loop.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> output (nums.size(), 1);
        for (size_t i = 1; i < nums.size(); i++){
            output[i] = nums[i-1]*output[i-1];
        }
        int postfix = 1;
        for (int j = nums.size()-1; j >= 0; j--){
            output[j] *= postfix;
            postfix *= nums[j];
        }
        return output;
    }
};

• First solution: O(n) time, O(n) extra space (two helper arrays).
• Two-pass solution: O(n) time, O(1) extra space (auxiliary) (only the output, plus one scalar).

8. Valid Sudoku#

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //i = row
        //j = col
        for (int i=0; i < 9; i++){
            unordered_map<int, int> for_row;
            unordered_map<int, int> for_col;
            for (int j=0; j < 9; j++){
                if (board[i][j] != '.'){
                    if (for_row[board[i][j]] < 1) for_row[board[i][j]]++;
                    else return false;
                }   
                if (board[j][i] != '.'){
                    if (for_col[board[j][i]] < 1) for_col[board[j][i]]++;
                    else return false;
                }
            }
        }
        unordered_map<int, unordered_map<int,int>> for_sqr;
        for (int i=0; i < 9; i++){
            for (int j=0; j < 9; j++){
                int current_sqr = (i/3)*3 + (j/3);
                if (board[i][j] != '.'){
                    if (for_sqr[current_sqr][board[i][j]] < 1){
		                for_sqr[current_sqr][board[i][j]]++;
	                } else return false;
                }
            }
        }
        return true;
    }
};

Problems I’ve faced#

• Okay so clearly when I read the question, I was blasted by the size of the sudoku. But I knew how they worked so I did come up with the ideas of checking duplicates in rows and columns each, one pass for each in O(n2) time. Hash maps!
• O(n2) is fine actually because the sudoku board is only 9x9 meaning only 81 operations needed.
• The problem was, how do we check the 3x3 squares?? After much thought of for loops, I realized this needed some trick and not a brute for looping for each 3x3 square in the sudoku board.
• A looked up at a hint in the problem, and it said that I could calculate the index (between 0-8) for each 3x3 square, just by using the row and column value of the current cell. It was (row/3)*3 + (col/3).
• At first I was like, wtf, how could I iterate through?
• But then, why do I have to iterate through? I could create a hash_map storing a hash_map connected to that square’s index. This nested hash_map would be the one checking duplicates.
• But I was unsure if I would be able to code it well so I ended up doing two passes.
• I also realized I had to put the for_row and for_col in the outer loop instead of the inner loop because it forgot at every cell lmfao.
• Of course, I had early returning the moment a number went above one.
• Oh! I had to change the condition of the duplicate from <2 to <1 because map[val] creates it in the hash map, and if a duplicate is seen it will push the value from 0 to 1 directly. The moment a duplicate is seen, <1 is false so it returns early.
• Now I’ll put the square pass in the main loop so there’s just ONE pass.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //i = row
        //j = col
        unordered_map<int, unordered_map<int,int>> for_sqr;
        for (int i=0; i < 9; i++){
            unordered_map<int, int> for_row;
            unordered_map<int, int> for_col;
            for (int j=0; j < 9; j++){
                if (board[i][j] != '.'){
                    if (for_row[board[i][j]] < 1) for_row[board[i][j]]++;
                    else return false;
                }
                if (board[j][i] != '.'){
                    if (for_col[board[j][i]] < 1) for_col[board[j][i]]++;
                    else return false;
                }
                int current_sqr = (i/3)*3 + (j/3);
                if (board[i][j] != '.'){
                    if (for_sqr[current_sqr][board[i][j]] < 1) {
	                    for_sqr[current_sqr][board[i][j]]++;
	                }
                    else return false;
                }
            }
        }
        return true;
    }
};

What can be done better?#

• Hashmaps are cool. But you know what’s cooler? Arrays. We can access elements in literally O(1) time.
• Similar to storing freq[26] when testing anagrams, we know that the numbers in the sudoku table are between 1-9 and rows, columns, and 3x3 squares are also from 0-8 (index).
• So we could store 3 matrices:
  • row_count[row r][what number we looking at, n] which tells the number of times a number n was seen in row r.
  • col_count[col c][what number we looking at, n] which tells the number of times a number n was seen in col c;
  • sqr_count[sqr s][what number we looking at n which tells the number of times a number n was seen in sqr s.
  • r, c, s all range from 0-8, and the number n itself too.
• Let’s code it!

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //i = row
        //j = col
        int sqr_c[9][9] = {0};
        int row_c[9][9] = {0};
        int col_c[9][9] = {0};
        for (int i=0; i < 9; i++){
            for (int j=0; j < 9; j++){
                if (board[i][j]=='.') continue;
                
                if (row_c[i][board[i][j]-'1']==0) row_c[i][board[i][j]-'1']++;
                else return false;

                if (col_c[j][board[i][j]-'1']==0) col_c[j][board[i][j]-'1']++;
                else return false;

                if (sqr_c[(i/3)*3+(j/3);][board[i][j]-'1']==0) sqr_c[s][board[i][j]-'1']++;
                else return false;
            }
        }
        return true;
    }
};

9. Longest Consecutive Sequence#

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        vector<int> counts;
        unordered_map<int, int> mapp;
        for (size_t i = 0; i < nums.size(); i++){
            mapp[nums[i]] = i;
        }
        int count = 0;
        
        for (int x : nums){
            if (mapp.find(x-1)==mapp.end()){
                count++;
                while (mapp.find(x+1) != mapp.end()){
                    count++;
                    x = x+1;
                }
                counts.push_back(count);
                count=0;
            }
        }

        int maxi = 0;
        for (int x : counts){
            maxi = max(x, maxi);
        }
        return maxi;
    }
};

Problems I faced#

• Upon seeing the requirement of the solution in O(n) and the obvious solution that came to mind was O(n2), I didn’t want to use nested loops.
• So? I tried to go for one for loop where I would change the index based on what next element I found.
• After writing it’s code, I realized that messing with indexes in for loops is almost ALWAYS bound for error. Because the condition that leaves the for loop is never coded inside the for loop manually (like in while) but is included in the for loop.
• Clearly, my solution was failing due to forever looping and reaching TLE.
• First example should have passed on my code [2,20,4,10,3,4,5] because when we reached the final element 5 i++ would have escaped the for loop. YET somehow my count value kept being 0 for some reason.
• Knowing well this wasn’t going to work, I looked up whether this problem with a nested loop would truly be O(n2) or not.
• I was looking for the worst case, something like [1, 3, 5, 7] or [1,2,4,5,7,8] and was thinking that this would for n*n/2 times. But reimagining it by writing it down, we ONLY get in the loop for specific elements, and run the nested loop ONCE for each number. Meaning each number is visited only ONCE. aka, O(n).
• Coded it, got it running.
• Didn’t face syntax issues much this time.

Why it works?#

• This solution is O(n) in both time and space, because the extra set we created consumes the space as n grows. Time because each element is visited once. But why?
• You see, we only start checking the consecutive-ness of elements IF we know that they are the start of that sequence. We check that by trying to find the number before the element and if there’s none, it would be the first of its possible list.
• Then we use the while loop to visit the elements of its consecutive list.
• Then the outer loops moves forward, but doesn’t initiate the inner loop since the consecutive elements (that aren’t the first element) will not be considered as a new list to discover. They only get visited because they had a first element before them.
• So assuming there are n elements in nums, then the outer loop does run n times. But the inner loop only runs when we find a first element, which reads the next say y consecutive elements (y operations). So each first element starts y operations. The middle elements don’t, so only 1 operation for them (the outer loop). We only start looking for middle elements AFTER a first element existed. MEANING we only do n operations + at most n operations for each first element we found. This isn’t n*(at most n) but n+ (at most n) which is basically, O(n).
• Every element is walked by an inner while loop at most once, ever, across the entire run.
• Because each number belongs to exactly one consecutive sequence, and that sequence is walked exactly once, from its unique start.

What can be made better?#

• Instead of saving it in a hash_map (which stored the index earlier and was useless here because we only want validity of presence of a number) we can store it in an unordered_set. We still have O(1) lookups, and no duplicates.
• Directly copy elements by using the syntax unordered_set<int> mapp(nums.begin(), nums.end()) man these hacks are nuts. This is same as a for loop (O(n)) but saves me from writing a for loop.
• Anyways, instead of saving things in a vector, we can update a variable of best_count and return that. Saves space complexity and an extra for loop.
• Here’s the final code:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        unordered_set<int> mapp(nums.begin(), nums.end());
        int best_count = 0;
        
        for (int x : mapp){
            if (mapp.find(x-1)==mapp.end()){
                int count=1;
                int curr = x;
                while (mapp.find(curr+1) != mapp.end()){
                    count++;
                    curr = curr+1;
                }
                best_count=max(best_count, count);
            }
        }

        return best_count;

    }
};

The two pointer approach is useful when you are tired of O(n2) solutions and multiple passes over the same data. You use two different pointers, and converge to the solution based on the problem. But the problem with it, is that the approach is same but framing is different for each problem. These can be categorized in three buckets:

1. Scan & Verify: When you use two pointers just for checking a condition (such as in Valid Palindrome).
2. Comparing against a target: When you use two pointers to look for a solution that satisfies a target. Whatever brings you closer to the target, go there (such as in Two Sum II).
3. Exchange-argument optimization: When you have no fixed target, but you’re optimizing a solution, such as looking for a maximum. Used in both Container with most water and Trapping Rain Water.

1. Valid Palindrome#

class Solution {
public:
    bool isAlpha(char& c){
        if (c > 64 && c < 91) {
            c = c + 32;
            return true;
        }
        if (c > 96 && c < 123) return true;
        if (c > 47 && c < 58) return true;
        return false;
    }
    
    bool isPalindrome(string s) {
        int n = s.size();
        int i = 0;
        int j = n-1;
        while (i<j){
            if (!isAlpha(s[i])) {
                i++;
                continue;
            }
            if (!isAlpha(s[j])){
                j--;
                continue;
            }
            if (s[i] != s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
};

Problems I faced#

• I mean. Strings. I know they are arrays, but that isn’t the problem anymore.
• This question was slightly different, because we were given alphanumeric characters only. They are all the english alphabets, and the numbers 0-9.
• I had to look up the ranges of these characters, and then I found out that the strings would contain spaces as well. So I thought let’s create a new function itself, which will check if it is alphanumeric or not.
• Even though the question said it was case-insensitive, I still converted the capital letters to small letters by adding 32 to the ascii values. (I forgot it was case insensitive but I don’t regret it).
• I forgot to add continue in the if conditions and ended up checking the equality each time even after i or j changed. I thought it would work without continue, because the if conditions before it ensured that i and j pointed to alphanumeric characters only.
• Two pointers isn’t new to me. The previous array questions had me doing things in one passes.

What can be done better?#

• Clearly this solution is inefficient. First off, I created a separate function that let’s me check for alphanumeric. I didn’t know the library function which is isalnum() from <cctype> library. And adding 32 to ascii values can be replaced with tolower().
• Then that function I wrote also changes uppercase to lowercase automatically, so even though I made it deliberately, it’s better to write readable code that doesn’t do what it’s name says it does. Again, if I did want uppercase values then I’d have removed it, but no one would know.
• Case insensitive means ‘A’ and ‘a’ are treated the same. So in this question, since both ascii values would still be different, I need to convert one into the other. If it was case sensitive, then I wouldn’t have to because I’d need to make sure ‘A’ matches only ‘A’ and not ‘a’.
• Then, one gotcha. Both isalnum() and tolower() require a unsigned char (non-negative) and char is sometimes negative too. This would throw an undefined behaviour (UB).
• Something called casting saves that. It converts signed stuff to unsigned stuff. So, we do isalnum(static_cast<unsigned char>(c)) and tolower(static_cast<unsigned char>(c)). This converts a negative c into the right ascii value (0-255). By conversion, we mean “Reading the same bits differently”
• Complexity? We only operated O(n) times. And O(1) space because we didn’t create anything.

About casting#

• Casting is done when you need to reinterpret a datatype into another data type.
• In C, we could typecast something with (datatype) expression like (int)myFloat but this is quite vague for the different reasons it can fail. So C++ adds 4 different types of casting.
• Static Casting: Converts between compatible/related types. Done during compile time.
• Dynamic Casting: Safely downcasts inside polymorphic hierarchies. These are in classes with atleast one virtual function. But since I can’t remember OOPs concepts, I will box this for later.
• Const Casting: Adds or removes const or volatile qualifiers. Meaning if I termed some variable as unchangeable, then changing that can cause issues in complex codes.
• Reinterpret Casting: This is low-level, aka close to machine language, aka playing with memory. It directs the compiler to interpret raw binary memory bits of an expression exactly as if it were a totally distinct data type.
• Anyways, we care about static_cast, useful for converting ints to floats, signed to unsigned, changes inheritance from a derived class to a base class. It checks at compile time, and if just isn’t possible (like int to struct) it won’t compile. But IT WILL COMPILE and not throw error if we did something that’s fine for a computer but logically not right. Like converting a double into an int. This will lose the decimal.
• Anyways, here’s the final codes.

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        int i = 0;
        int j = n-1;
        while (i<j){
            if (!isalnum(static_cast<unsigned char>(s[i]))) {
                i++;
                continue;
            }
            if (!isalnum(static_cast<unsigned char>(s[j]))){
                j--;
                continue;
            }
            if (tolower(static_cast<unsigned char>(s[i])) != tolower(static_cast<unsigned char>(s[j]))) return false;
            i++;
            j--;
        }
        return true;
    }
};

2. Two Sum II - sorted array#

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0;
        int j = nums.size()-1;
        while(nums[i] + nums[j] != target){
            int sum = nums[i] + nums[j];
            if (sum > target){
                j--;
                continue;
            }
            if (sum < target){
                i++;
                continue;
            }
        }
        return {i+1, j+1};

    }
};

Problems I faced#

• NONE! The code run perfectly and got submitted in one try.
• At first I thought I’d use the slow/fast thingy, but it was skipping elements in my head. Then binary search where I’d half i or j but that still skipped elements and never known whether increasing i or decreasing j would give a higher or lower target. So didn’t attempt that either.
• Simply, increase i and decrease j, array is sorted so we know we are converging by checking the inequality against sum. We didn’t have that in normal two sum, where numbers were random and we didn’t know which pointer to change.

What can be made better?#

• This solution worked because we were guaranteed a solution. But if there wasn’t, the equality would need to be i<j so we know it ends even after checking all possible elements through individual work of i and j.
• Instead of continue, we can cleanly write if else statements since we don’t check AFTER the ifs but before them.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0;
        int j = nums.size()-1;
        while(i<j){
            int sum = nums[i] + nums[j];
            if (sum == target) return {i+1, j+1};
            else if (sum > target) j--;
            else i++;
        }
        return {};
    }
};

3. 3sum#

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<vector<int>> answer;
        int i = 0;
        while (i < nums.size()-2){
            int j = i+1;
            int k = nums.size() - 1;
            while (j < k){
                if (nums[i] + nums[j] + nums[k] < 0) j++;
                else if (nums[i] + nums[j] + nums[k] > 0) k--;
                else {
                    answer.insert({nums[i], nums[j], nums[k]});
                    j++;
                }
            }
            i++;
        }

        vector<vector<int>> output;
        for (const auto& x : answer){
            output.push_back(x);
        }
        return output;
    }
};

Problems I faced#

• A lot of problems were faced. At first, I was so confused on what to do. Then thought of the approach of i++, j—, and loop between them. I was trying really hard to not have a O(n3) solution. But this was skipping elements again because i and j are moving to the center at the same rate and we would miss elements that are skewed on the backward side. Like elements that didn’t get included due to change in i or j before we tried all combinations.
• However, this error only came after it worked for a few test cases and gave me a duplication output. So, in the final output vector I needed unique elements. I thought I’d create an unordered_set but apparently it doesn’t store and compare vectors well. I looked up, it was asking me to create a custom differentiator function which I have no idea about, but then I was told that normal set works with vectors and I did that.
• The final solution I conjured up where I’d have one outer loop for i and do the same two pointer approach for two sum on a sorted array.
• Time complexity: O(n2.logm) where m is number of elements in set. Insert operation is costing me. Space: O(n)
• I am completely aware that this solution is inefficient. But I’m at least glad I solved it myself.

What can be made better?#

• Alright so my solution can be improved by skipping the duplication. Set doesn’t allow duplicates yes, but due to insert operation we were suffering. Instead we can just skip the duplicate numbers AS we encounter them in the array.
• The initial check for i we check whether the previous number at i-1 is same as i and if it is, we skip it.
• When we find a new i then start with two pointers j and k, do the testing and when we have found a triplet, it’s possible the elements near j and k are same (since array was sorted) and we should skip them since they would only form duplicate triplets.
• Another skipping mechanic, the moment i points to something more than 0, then j and k are also greater than 0 and we can possible not have any more triplets. So we end early.
• No set this time, only a vector. So O(n) space. O(n2) time because no insert operation.
• Here’s the more efficient solution.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> output;
        int i = 0;
        while (i < nums.size()-2){
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i-1]) {
                i++;
                continue;
            }
            int j = i+1;
            int k = nums.size() - 1;
            while (j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) j++;
                else if (sum > 0) k--;
                else {
                    output.push_back({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                    while (j<k && nums[j] == nums[j-1]) j++;
                    while (j<k && nums[k] == nums[k+1]) k--;
                }
            }
            i++;
        }
        return output;
    }
};

4. Container With Most Water#

class Solution {
public:
    int maxArea(vector<int>& h) {
        int n = h.size();
        int i = 0;
        int j = n-1;
        int maxi = 0;
        while (i < j){
            int area = (j-i)*min(h[i], h[j]);
            maxi = max(area, maxi);
            if (h[i]<h[j]) i++;
            else j--;
        }
        return maxi;
    }
};

Problem I faced#

• I was not able to solve this problem myself. After trying really hard to think of a solution, I only managed to think of the idea of moving TOWARDS the height that gave me a higher water value. If i++ gave me a higher water than j— than I’d move forward with i++ and not j— then repeat, while storing the absolute max. But this didn’t work. It wasn’t converging to the best pair.
• I had to look up the hints in the problem. It told me that you only move the index that was the lesser one than the other. Because if we didn’t move it, the absolute max that this height can give is lesser than before because width would be lower. So we need to change this one, and keep the other longer height same. Slowly, both height bars would be bigger than before.

Why it works#

• You see, this works because in the two pointer approach, convergence is only guaranteed if you do something that’s better, or if you do something that is the reverse of what isn’t working. This problem is the latter. Because moving the lower tower is the only way you can have a different answer than the current one, which might be better. If we moved the higher tower first, the score would still be at most the other lower height (but lower width, so probably worse!).
• Since we did the opposite, and also checked each possibility too (because either i or j moves until we reach the best, because there will always be one lower tower) we converged.

5. Trapping rain water#

class Solution {
public:
    int trap(vector<int>& height) {

        int n = height.size();
        vector<int> water;
        for (int i =0; i < n; i++){
            int l=0;
            int r=0;
            for (int j = 0; j < i; j++){
                l = max(l, height[j]);
            }
            for (int j = i+1; j < n; j++){
                r = max(r, height[j]);
            }
            water.push_back(max(min(l,r)-height[i], 0));
        }
        int sum = 0;
        for (int x : water){
            sum += x;
        }
        return sum;
    }
};

Problems I faced#

• Well clearly this is a hard problem. I was completely lost on what to do.
• I had to look up at the hints, which gave me the idea of how to calculate the height of water at each index. It clicked, and wrote this solution
• But it pains me that this is an O(n2) solution. The question said it should be at most or better than O(n).
• My solution does not contain anything related to two pointers.
• But wait, I can replace it! Let’s code it!!!!

class Solution {
public:
    int trap(vector<int>& height) {

    int n = height.size();
    vector<int> water;
    int l=0;
    for (int i=0; i < n; i++){
        l = max(l, height[i]);
        water.push_back(l);
    }
    // now water vector contains best heights from the left
    // we can directly compute right best and amount of water now
    int r = 0;
    for (int i=n-1; i >=0; i--){
        water[i] = (max(0, min(r, water[i])-height[i]));
        r = max(r, height[i]);
    }

    int sum = 0;
    for (int x : water){
        sum += x;
    }
    return sum;
    }
};

• LETS GOOOOOO!!!
• But this is still not using two pointer approach. This is still two passes. What else can we think of?

What can be done better?#

• Yeah so this better solution is quite hard to see.
• First see the solution.

class Solution {
public:
    int trap(vector<int>& height) {
    int n = height.size();
    int totalwater = 0;
    int l = 0;
    int r = n - 1;
    int leftMax = 0;
    int rightMax = 0;
    while (l<r){
        if (height[l] < height[r]){
            leftMax = max(leftMax, height[l]);
            totalwater += leftMax - height[l];
            l++;
        }
        else {
            rightMax = max(rightMax, height[r]);
            totalwater += rightMax - height[r];
            r--;
        }
    }
    return totalwater;
    }
};

• We only move the index of the bar with the lower height again.
• We only process the left side when height[l] < height[r].
• So whatever we have at l, we calculate the water there. leftMax contains the best height before current l. We calculate total water by leftMax - current_height without looking at the right side. Why? Because it was guaranteed that height[l] < height[r] making left the only bottleneck. You’d wonder what if height[r] was lower than leftMax? which is the confusing part. But the solution would never reach that point because we cannot get leftMax > height[r]. The movement of l and r is such that that condition never arrives. leftMax must’ve been processed before, meaning l was at leftMax sometime before, and we only got leftMax value when some height[r] was already bigger. Now r didn’t move, and it only moves when height[l] is higher than height[r] which can only be lesser than or equal to the previous rightMax. So leftMax never grew past it’s big height[r] and is already higher than current height[l]. Meaning we right side is bigger than left side, and left side is the bottle neck.