DEV Community: Nayan Pahuja

Cracking the Code: Unlocking Password-Protected PDFs with Masked Brute Force

Nayan Pahuja — Sun, 01 Oct 2023 17:44:02 +0000

Hey Guys! This article is something I am not used to writing so, If I miss any spots, please feel free to correct me in the comments. I am looking forward to constructive feedback.

With that in mind, Let's start the article.

We will be using the following resources for this article, I will be linking them with their explanation incase anyone wants to follow along.

Introduction:

John the Ripper

John the Ripper is an incredible open source software designed for the purpose of recovering lost or forgotten passwords through various password cracking techniques. It is highly versatile and can be used to crack a wide range of password types, including those stored in various cryptographic formats and hash algorithms.

We are going to work with the Jumbo version of JohnTheRipper. This is a community-enhanced, "jumbo" version of John the Ripper. It has a lot of code, documentation, and data contributed by the user community. This is not "official" John the Ripper code.

HashCat

Hashcat is also another incredible open source software password cracking tool that is widely used by security professionals, penetration testers, and researchers to recover passwords from various types of hashed data.
It is known for it's wide support for multiple hash algorithms and fast speed.

Setup the environment:

Fun Story: I am writing this article because I needed to crack a password today for a document that was emailed to me, but I couldn't open it.

John The Ripper:

Download Windows binaries for Jumbo version and place it in the users directory.

Install Perl

We are also going to need to install Perl programming language for this to run JtR.
Download the Strawberry version of Perl, the link to which can be found here: Perl

Download the installer according to your respective bit for your desktop/laptop.

Note: Remember to restart your laptop after installing perl.

Download HashCat:

Download the Hashcat binaries and place it in a directory. For convenience I am going to place it in users as well.

Cracking the password:

Make sure to unzip the all the stuff that we have downloaded.

Now let's get to the magic part.

Visit the directory where you placed John The Ripper.

Change your current directory to run using cd run.

You can follow the commands as I did above to get to the directory.

If you run the command dir in windows cmd and ls in UNIX, you can see all the directories features that Jack the Ripper offers.

Out of this we need the command pdf2john.

John the Ripper is primarily focused on password cracking and hashing-related tasks, and it doesn't directly handle PDF cracking. To work with a password-protected PDF file in John the Ripper, you first need to create a hash file using the 'pdf2john.pl' tool, which is available in the 'run' directory after compiling John the Ripper from its source code. This Perl script tool allows you to extract the hash (metadata information) from the PDF file and save it to a new file using the following command:

I have a test pdf by the named pdf here which is protected by the password 2020!.
You must place your pdf inside the run directory of Jack The Ripper for convenience or specify the path in the command. I am going to do the earlier here.

If you check the run directory with your file explorer you would see something like this in it.

We only need the hash key not the file name so I am going to remove that from our hash key and place the key.txt in hashcat directory.

We are done with the work of John The Ripper now. We can proceed with using Hashcat for further process.

Hashcat:

We are going to use the masking approach for this the documentation to which can be found here:

You can open another terminal for this or use the same and change your directory to this.

Run the command:

hashcat.exe -h

to find about various attributes you can select in hashcat.

You might see something like this:

Let's get a little understanding of what Brute Force is first.

Imagine to open the door you needed a key and you had 1000 keys with no information. You would have to go through every key possibly hitting the right one because you know it's one of these keys that unlock it. You will have to try every possible key.

Same as you would in say a 3 digit lock you can actually go through all the combinations 000--->999.

But if we were to increase the digits, possible include characters this would be very hard.

So if we have some information even very little information such as the number of characters, what type, lowercase, uppercase digits etc can help bring down our possibilities from billion to millions!.

So I am going to take this hint here that I know the password will be of length 5 with 4 numerical digits and 1 special character.

What we need to utilize hashcat here is use this command

hashcat.exe -a 3 -m 10500 key.txt ?d?d?d?d?s

Here is a breakdown:

a means: Attack Mode-> Brute force in this case.
m means: Hash Type
key.txt is our file name
?d?d?d?d?s means that the first four characters are to be of type digits and last is a special character.

The result might be something like this.

Incase you are trying it on some other pdf file the results might take time accordingly.

Retrieving the password:

Now for the final step. Open the potfile using a notepad and you would see something like this:

What is a Potfile?

The potfile is only created after at least one hash has been cracked successfully. The directory does exist but no potfile there. Cracked over a million of hashes already and hashcat removes already cracked hashes.

The 2020! is our password!.

Yay!. We have successfully cracked a password.

Conclusion:

In the digital age, password security is of utmost importance, and sometimes, it becomes necessary to recover lost or forgotten passwords. In this article, we explored two powerful open-source tools, John the Ripper and Hashcat, which are invaluable resources for security professionals, penetration testers, and researchers.

This is it for this article!. Thanks for reaching the end. Please feel free to drop comments below, I'll be sure to reply!.

DAY 108 - Find Duplicate

Nayan Pahuja — Tue, 19 Sep 2023 18:26:51 +0000

Hey Guys! Welcome back to another 100DaysOf Code day.
We are going to do another daily leetcode question today.

Question: Find Duplicate

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Examples:

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Understanding the Problem

Before diving into the code, let's break down the problem and understand what's expected:

You are given an array nums containing n + 1 integers.
Each integer in the array is between 1 and n (inclusive).
There is only one integer that appears more than once in the array.
Your task is to find and return this duplicate integer.

The Approach

To efficiently solve this problem, we can use the Floyd's Tortoise and Hare algorithm, which is also known as the cycle detection algorithm. Here's how it works:

We initialize two pointers, slow and fast, both initially pointing to the first element of the array.
We use a loop to advance these pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This simulates two runners racing along the array.
If there is a duplicate number in the array, the pointers will eventually enter a cycle, meaning they will meet at the same position.
Once the pointers meet inside the cycle, we reset one of the pointers, let's say fast, to the beginning of the array, while keeping the other pointer (slow) inside the cycle.
We then advance both pointers at the same rate (one step at a time). When they meet again, it will be at the entrance of the cycle.
The position where the two pointers meet for the second time is the location of the duplicate number.
We return this duplicate number as our result.

Code:


class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];

        } while(slow != fast);

        fast = nums[0];

        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
    return slow;
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity: The Floyd's Tortoise and Hare algorithm runs in O(N) time, where N is the length of the array. This is because both pointers move through the array at different speeds, but the fast pointer covers the cycle at most twice.
Space Complexity: We use only a constant amount of extra space to store the slow and fast pointers. Therefore, the space complexity is O(1).

DAY 107 - Daily Temperatures

Nayan Pahuja — Mon, 18 Sep 2023 15:15:49 +0000

Hey Guys!, Welcome to DAY 107 of #100DaysOfCode challenge.
Let's get right into our question.

Question: Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Examples:

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Problem Breakdown:

We have been given an array temperatures which contains temperatures on n different days.
We need to find out for the i'th day , how many days do we need to wait to experience a temperature greater than it. If we can't find a temperature warmer than it, then we must return 0.
So the question is pretty straightforward, let's see how we can solve this.

Intuition:

We can go through every temperature using a for loop and then we can use another loop to find the temperature that is greater to our current temperature.
We can use this approach but it is of the order (N²), so we can probably do better than this.
Let's look at it this way, at once we need to maintain how much data, we definitely need the prevDay and prevTemp for comparison and we need the current day as we are traversing through.
Surely we have a data structure we can use to remember our previousTemperatures. It should be stack here as we can use extra memory.
We will keep temperatures in our stack, and if we encounter a greater value, we shall subtract the days and push them into our answer.
But for sure, we will be faced with the challenge in which our stack would be holding decreasing temperatures,
For that, suppose we do encounter a temp greater than current top of the stack but not all the members in the stack we need to pop our stack until we have found the element less than equal to the current top.

Approach:

To solve this problem efficiently, we can use a stack to keep track of the indices of the temperatures in the list. Here's the step-by-step approach:

We initialize an empty stack st to store pairs of (index, temperature).
We also initialize an empty vector answer of the same size as the input list to store the number of days to wait for each day.
We iterate through the input list of temperatures, where i represents the current day.
For each day, we check if the stack is not empty, and the temperature at the top of the stack is less than the current temperature. If this condition is met, it means we have found a warmer day for the day at the top of the stack.
We pop elements from the stack and calculate the number of days to wait for each of them. For each popped element (prevDay, prevTemp), we calculate i - prevDay, which represents the number of days to wait until a warmer temperature is encountered.
We update the corresponding position in the answer vector with the calculated number of days.
Finally, we push the current day and temperature onto the stack and continue to the next day.
After processing all the days, we return the answer vector, which contains the number of days to wait for each day.

Code:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();

        // pair: [index, temp]
        stack<pair<int, int>> st;
        vector<int> answer(n);

        for (int i = 0; i < n; i++) {
            int currDay = i;
            int currTemp = temperatures[i];

            while (!st.empty() && st.top().second < currTemp) {
                int prevDay = st.top().first;
                int prevTemp = st.top().second;
                st.pop();

                answer[prevDay] = currDay - prevDay;
            }

            st.push({currDay, currTemp});
        }

        return answer;
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

Time Complexity: We iterate through the input list once, performing constant-time operations for each day. Therefore, the time complexity is O(N), where N is the number of days.
Space Complexity: We use a stack to store at most N elements in the worst case (when temperatures are strictly increasing). Additionally, we use the answer vector of size N. Thus, the space complexity is O(N).

DAY 106 - Next Greater Element I

Nayan Pahuja — Sun, 17 Sep 2023 16:26:54 +0000

Question: Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1is a subset of nums2.

For each 0 <= i < nums1.length, find the index jsuch that nums1[i] == nums2[j] and determine the next greater element of nums2[j]in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:

4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.

2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Problem Breakdown:

Before we dive into the code, let's break down the problem and understand what's expected:

We have two arrays, nums1 and nums2, of non-negative integers.
Each element in nums1 is present in nums2.
For each element in nums1, we need to find the next greater element in nums2.
If there is no greater element in nums2, we should return -1 for that element in the result array.

Approach:

To solve this problem efficiently, we can use a stack and a hash map. Here's the step-by-step approach:

We initialize an empty stack s and an empty unorderd_map mp.
We traverse through nums2, which serves as our parent array to find the next greater elements.
In each iteration, we compare the current element, it, with the top element of the stack (s.top()). If it is greater, we update the hash map mp with the mapping of the top element of the stack to it. We also pop the top element from the stack because we have found the next greater element for it.
After processing nums2, we have a complete mapping of each element to its next greater element in mp.
We initialize the result vector res with the same size as nums1, filled with -1.
We iterate through nums1 and check if the element exists in mp. If it does, we update the corresponding position in res with the next greater element found in mp.
Finally, we return the res vector, which contains the next greater elements for each element in nums1.

Code:


vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> mp;
        stack<int> s;
        for(auto it : nums2){
            while(!s.empty() && s.top() < it){
                mp[s.top()] = it;
                s.pop();
            }
            s.push(it);
        }
        vector<int> res(nums1.size(),-1);

        for(int i = 0; i < nums1.size(); ++i){
            if(mp[nums1[i]]){
                res[i] = mp[nums1[i]];
            }
        }
        return res;
    }

Time and Space Complexity:

Let's analyze the time and space complexity of our solution:

Time Complexity: The solution processes both nums1 and nums2 exactly once, so the time complexity is O(N1 + N2), where N1 is the length of nums1, and N2 is the length of nums2.
Space Complexity: We use a stack and a hash map to store intermediate results. The space complexity is O(N2) in the worst case, where N2 is the length of nums2.

Version Control Systems and Git Part-2

Nayan Pahuja — Sat, 16 Sep 2023 17:46:36 +0000

In the last post we talked in brief about how Git takes snapshots of the directories we are working in , how the commits we do are actually categorized into some types of data objects and they are not really stored in a linear fashion. We did capture the essence of what Git does but we were still left hanging with little to no information about commits, SHA1 encryption that git uses and git commands. So let's get right back onto track. Incase you didn't read the first post, I would recommend reading that first as it's a continuation.

.git folder

Attempting to create a good distributed version control system within a mere week is an impossible task. However, what one can successfully design during the time is a fundamental data model.

So, what precisely does Git's data model entail? To delve into this topic, we must delve into the enigmatic .git folder.

In your ./git folder , it contains a folder called objects which is essentially nothing but your object can be either a commit, a tree, a blob, or a tag. They’re compressed with zlib, but we can extract and examine the objects easily.

Git Data Model as pseudo code

Last time we mentioned the terms such as blob(Binary Large Objects), commits, snapshots, tree and more.
Let's expand a little more on this data model internally of git.

// a binary large object is a file or say a bunch of bytes
type blob = array<byte>

// a folder/directory contains signed files and directories
type tree = map<string, tree | blob>

// a commit is an abstracted data object model with history to parents, author, the commit message, and the current snapshot basically the metadata of commit
type commit = struct {
    parents: array<commit>
    author: string
    message: string
    snapshot: tree
}

This is basically how git's data is modelled.

Git Objects and content-definitions

At some point this actually has to be created into data on disks.

Git defines objects which can be anything of the prescribed such as a blob, tree or commit

type object => tree | commit | blob

But what git actually maintains on disk is also a map to the hash of the object not just the object itself.

In git all data objects are content-addressed by SHA1 hash.

objects = map<string,object>
def store(object):
    id = SHA1(object)
    objects[id] = object

def load(id):
    return objects[id]

In case you don't know what SHA1 or Hashing is, you can think of it as making the data's or say the object's content and do it's addressing into a finite string. This helps us in addressing large amount of data's into small strings.

In practice commits don't actually contain the objects or snapshots for that matter but they have actually pointers to the obects location.

Blobs, trees, and commits are unified in this way: they are all objects. When they reference other objects, they don’t actually contain them in their on-disk representation, but have a reference to them by their hash.

In the realm of cryptography, SHA-1 (Secure Hash Algorithm 1) serves as a hash function. It operates by taking an input and generating a 160-bit (equivalent to 20 bytes) hash value, commonly represented as a 40-character string composed of hexadecimal digits.

Fun Fact:

Generating two identical SHA-1 hashes is an exceptionally rare occurrence, nearly approaching the realm of impossibility. To put this into perspective, imagine having to generate more hash codes than there are grains of sand on all the beaches across the entire Earth before the likelihood of encountering two identical hashes even becomes a consideration.

If we further use the command git cat-file -p <hashId> example something like

 git cat-file -p 4448adbf7ecd394f42ae135bbeed9676e894af85

The tree itself contains pointers to its contents, index.txt (a blob) and blogExample(a tree). If we look at the contents addressed by the hash corresponding to index.txt with git cat-file -p <hashId>, we get the following:

This Side Nayan

References

Now any normal human would not be able to remember 40characters long random sequences for having a pointer to its object but so then how do we call it.

Well Git actually maintains another set of references which gives human name to those SHA1 generated strings to actually have addressable pointers for the end user.

reference_map = map<string,string> (string1  is human name and string 2 is hash)


def store_reference(name, identifier):
    reference_map[name] = identifier

def retrieve_reference(name):
    return reference_map.get(name)

def load_reference(name_or_id):
    if name_or_id in reference_map:
        return load(reference_map[name_or_id])
    else:
        return load(name_or_id)

Unlike objects, which are immutable, references are mutable (can be updated to point to a new commit). For example, the master reference usually points to the latest commit in the main branch of development.

With the help of these references git can actually maintain human-readble names like master main and so on.

Repositories

In essence, a Git repository can be roughly defined as a collection of data objects and references.

When we examine the repository on disk, we find that it comprises only two fundamental elements: objects and references. This straightforward concept encapsulates Git's entire data model. Essentially, all Git commands can be mapped to actions that manipulate the commit Directed Acyclic Graph (DAG) by either adding objects or updating references.

The next time you enter a Git command, it's valuable to contemplate how that command influences the underlying graph data structure. Conversely, if you're aiming to achieve a specific alteration within the commit DAG – for instance, "discard uncommitted changes and set the 'master' reference to point to commit 4d123f6w" – you'll likely discover a command tailored to that purpose. In this particular case, the commands would be: gitcheckout master followed by git reset --hard 4d123f6w.

The Staging Area

The concept of staging area is quite brilliant when you understand it although it is separate from Git's data model but is an integral part of how commits are created.

Instead of having a single "create snapshot" command that captures the current state of everything and take the data again and repeat the whole story Git takes a different approach. It provides a way to choose precisely what changes we want to include in the next snapshot. This selection process is done through something called the "staging area."

The staging area lets us pick and choose which modifications should go into the next snapshot. This flexibility is useful when we have multiple changes in progress or when you need to create a commit that includes some changes while excluding others.

Since this post has already gone I won't be covering the git commands in depth. I will be linking down the best resources to read more about git and how git commands work.

Now that we have gotten a little understanding how git works, the commands should not feel like magical incantations but some very simple CLI commands.

In practice git uses delta compression and many more stuff to achieve what it is today. This is just an outline to the fancy technology used.

Conclusion:

In conclusion, through this two part series I have tried to provide some valuable insights into Git's fundamental data model, the role of the .git folder, and how Git objects are organized using SHA-1 hashes. We've learned about the significance of references in providing human-friendly names to commits and explored the concept of the staging area for precise control over what goes into each snapshot. Understanding these core aspects of Git's inner workings is crucial for efficient version control. To further enhance your Git proficiency, you can refer to the recommended resources mentioned in the post.

Resources:

Pro Git
I highly recommend reading first few chapters of the books and then looking into some advanced stuff.
GitHub: Git is not GitHub. GitHub has a specific way of contributing code to other projects, called pull requests.
Other Git providers: GitHub is not special: there are many Git repository hosts, like GitLab and BitBucket.
Git For Computer Scientists
Missing Lectures VCS
Git is Simpler than you think

Sources:

This series was heavily inspired by the Missing Semester Lecture on Youtube which I will leave the link down below and a few very good articles. I have tried to incorporate the parts I think were important and best from each.

DAY 105 - 155. Min Stack

Nayan Pahuja — Sat, 16 Sep 2023 13:48:52 +0000

Hey Guys! Welcome back to another day. Today we will be moving onto stacks from our linked lists and we are back with a very good question.

Question: 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example 1:

Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-3,null,0,-2]
Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Understanding the MinStack:

push(val): This operation adds an element, val, to the stack. It also needs to keep track of the minimum element in the stack.
pop(): This operation removes the top element from the stack.
top(): This operation returns the top element of the stack without removing it.
getMin(): This operation returns the minimum element currently present in the stack in constant time.

Approach:

To implement the MinStack, we can use two separate stacks: one to store the actual elements (st) and another to keep track of the indices of minimum elements (miniVals). Here's how our approach works:

We maintain two vectors, st and miniVals, to represent the stack and store the indices of minimum elements, respectively.
When pushing a new element onto the stack (push(val)), we compare it with the current minimum element. If it's smaller, we push the index of the new element onto miniVals. This way, we always have a reference to the index of the minimum element in the stack.
When popping an element from the stack (pop()), we simply remove the top element from st. If the index of the minimum element (miniVals.back()) matches the index of the element being removed, we also remove it from miniVals.
Retrieving the top element (top()) is straightforward; we return the last element of st.
To get the minimum element (getMin()), we use the index stored in miniVals to access the corresponding element in st.

Code:


class MinStack {
public:
    vector<int> st;
    vector<int> miniVals;
    MinStack() {
    }

    void push(int val) {
        if(miniVals.empty() || val < st[miniVals.back()]){
            miniVals.push_back(st.size());
        }
        st.push_back(val);
    }

    void pop() {
        st.pop_back();
        if(miniVals.back() == st.size()) miniVals.pop_back();

    }

    int top() {
        return st.back();
    }

    int getMin() {
        return st[miniVals.back()];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Time and Space Complexity

Time Complexity: Each of the operations (push, pop, top, and getMin) takes constant time, O(1), as we are only performing basic vector operations, which have constant time complexity.
Space Complexity: The space complexity is O(N), where N is the number of elements stored in the stack. This space is used to store the actual elements in st and the indices of minimum elements in miniVals.

Version Control Systems - Part 1

Nayan Pahuja — Fri, 15 Sep 2023 18:46:32 +0000

Millions of developers today use Git or Git Hub. It has become a core part of any kind of programmer's day after their work has been done. If you were applying for a development position today, it would be a prerequisite that you understand git and Github or some kind of version control system.

I remember 2 years back when I first started basic development, coding, and stuff in my first year of college that I interacted with this. VCS is something developers can't think of working without today and yet no college university explicitly covers VCS.

I will try to make this into a two-part series on Version Control Systems and subsequently the de facto standard for VCS today git.
In this post I will be trying to cover how it works and what exactly happens to your data, so Let's get started.

Version Control Systems:

What are Version Control Systems?

We have been using VCS for a long time now. To put it to a definition:

Version Control Systems are tools that are used to track changes to source(original) code changes or the collections of files and folders around it.

As the name implies Version Control Systems helps us maintain a history of changes also facilitating collaboration at the same time.

Gone is the time we would need to manually change our existing codebase line by line when working with some other member. VCS does all of that and more for us today.

VCSs track changes to a folder and its contents in a series of snapshots, where each snapshot encapsulates the entire state of files/folders within a top-level directory. VCSs also maintain metadata like who created each snapshot, messages associated with each snapshot, and so on.

Why Version Control Systems?

Well, we have all played games and never played them in one sitting(well sometimes), So what do we do? We save our game to our last checkpoint log in the next day and continue from the same spot or if we make a mistake we could start from our last checkpoint and start again. Why could we not do that with our code? Well, we have already been doing it, that's exactly what VCSs are doing, We can easily track what we have been doing wrong and where we went off right or try new things without breaking the existing working code.

Types of Version Control Systems and their History:

Local Version Control Systems:
- History: Local VCSs were some of the earliest form of version control. They operated on a single computer and kept track of changes made to files using a simple database or file system.
Centralized Version Control Systems (CVCS):
- Examples: Concurrent Versions System (CVS), Subversion (SVN).
- History: CVCSs introduced the concept of a central server that stored the repository. Developers could check out code from this central location and commit their changes back to it. While it improved collaboration compared to local VCSs, it had limitations in terms of scalability and offline access and could also lead to some conflicts more easily.
Distributed Version Control Systems (DVCS):
- Examples: Git, Mercurial, Bazaar.
- History: DVCSs represent a significant evolution in version control. Instead of relying on a central server, each developer has their own local repository, which is a complete copy of the entire project history. Developers can work offline, branch easily, and commit locally before pushing changes to a shared central repository.

Features of Modern VCSs

It’s an invaluable tool for seeing what other people have changed, as well as resolving conflicts in concurrent development.

Who authored this module?
When was this specific line in the particular file last modified, and who made the changes? What was the reason behind the modification?
Within the past 100 revisions, when and for what reason did a specific unit test cease to function properly?

While there exist many VCSs git is the de facto standard for today's version control systems.

This fun comic by xkcd completely debunks half of the developer community when they start out and I certainly have done this as well.

Git

Let's use git to understand a little bit how modern day DVCS work and let's explore how git works internally a little bit.

When I began learning Git, I found that starting with the command-line interface was quite confusing. Instead of grasping the underlying concepts, I ended up memorizing a handful of commands and relied on them like magic spells whenever I ran into problems.
I am very confident I am not alone who has done this.

Git may not have the prettiest interface, but its core design and ideas are elegant. Instead of just memorizing commands, it's helpful to start from the basics, understanding Git's data model first, and then getting into the command-line part. Once you grasp the data model, using Git commands becomes more logical instead of feeling like chanting magical incantations and it works somehow.

Git Data Model:

While there are numerous ad-hoc approaches to version control, Git stands out with its carefully designed model that underpins essential version control features such as history maintenance, branch support, and collaborative capabilities.

Snapshots:

Imagine you are doing work in some parts but the catch is you can't exactly remember where you left the work last.
What you can do is take a picture of where you working last time and next time you come back to it you can refer to that picture and start seeing changes from there.

Every time you commit git takes a snapshot(not exactly a picture the example was just for understanding)
Git also views what was the state of your code in the last snapshot which exists and shows the changes currently made by simply their differences.

In Git terminology, a file is called a “blob” (Binary Large Object), and it’s just a bunch of bytes. A directory is called a “tree”, and it maps names to blobs or trees (so directories can contain other directories). A snapshot is the top-level tree that is being tracked.

Let's make some files and folders to understand this in a better way.

~$ mkdir blogExample
~$ cd blogExample
~/blogExample$ echo "Hey This Side Nayan" > index.txt
~/blogExample$ git init
~/blogExample$ git add index.txt
~/blogExample$ git commit -m "First commit, added introduction."

For example, we might have a tree as follows:

<root> (tree)
|
+- blogExample(tree)
|  |
|  + index.txt (blob, contents = "This Side Nayan")
|

Version History:

How should a VCS relate version history, which is one of the more crucial parts of a VCS. We can always take a linear history take something like this:

But git doesn't exactly work in this way, It uses a common Data Structure known as Directed Acyclic Graph to store the snapshots.

What this essentially means in Git is that each snapshot I create has a reference to a set of "parents," which are the snapshots that came before it. It's a set of parents, not just a single one (as you would have in a linear history), because a snapshot can be connected to multiple parents. This can happen, for instance, when I merge two parallel branches of development.

Though I have used the word commit in the images, what those circle essentially represent are Snapshots taken in place by git.

This might correspond to, for example, two separate features being developed in parallel, independently from each other. In the future, these branches may be merged to create a new snapshot that incorporates both of the features,

This is essentially what branching is.

Commits in Git are immutable. This doesn’t mean that mistakes can’t be corrected, however; it’s just that “edits” to the commit history are actually creating entirely new commits, and references are updated to point to the new ones.

Github Origin:

You can create a Git repository on your own computer and manage it locally, taking advantage of Git's features such as branches and commits. However, if you intend to collaborate with others on the project, this approach won't suffice. An alternative is to copy the entire project to another computer and regularly export changes, sending them back and forth for updates. Nevertheless, this method is far from ideal. What you'll end up with is a centralized location where project data is stored, and it becomes the hub for downloading and uploading changes and commits. This central location is referred to as "origin." You have the option to host it on your personal server, but there are also many free solutions available, such as GitHub, that you can use for this purpose.

Conclusion Part 1:

While there are numerous features and functionalities in VCSs(git and more), such as committing, pushing changes, merging, and more, the main takeaway from this post should be a fundamental understanding of what Git is. For those encountering version control systems for the first time, the initial confusion can be overwhelming. However, I hope this post has provided you with a clear idea of how VCSs operate and why it is an invaluable tool in the world of software development.

I will be covering more of Object Data Model of git, how it uses SHA1 hashing to store the data and how commits are actually not objects but are pointers to snapshots and such more things including git commands.

DAY 104 - Merge k Sorted Lists

Nayan Pahuja — Fri, 15 Sep 2023 09:07:57 +0000

Hey Guys!, Welcome to DAY 104 and we are continuing on our journey to master linked list. Today we are back with a hard interesting question. So Let's get right down to it.

Question: Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Examples:

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Question Breakdown:

Ok so despite it being tagged as the hard problem is quite easy to understand.
The description is asking us to make an merge all the given linked lists in a vector which are already sorted in order.
So what we have to do is basically merge all the lists but If the size is too big, we can't be declaring pointers for every list right.

The Approach

To solve this problem efficiently, we can use a divide-and-conquer strategy. Here's a step-by-step explanation of our approach:

Handle Edge Cases:
- If the input array of linked lists is empty, we return nullptr, indicating an empty list.
- If there's only one linked list in the array, we return it as the result.
Pairwise Merge:
- We start by dividing the array of linked lists into pairs and merging each pair into a single list.
- For example, if we have k linked lists, we pair the first list with the (k/2 + 1)-th list, the second list with the (k/2 + 2)-th list, and so on.
- We do this merging iteratively until we have only one merged list remaining.
Merging Two Lists:
- To merge two sorted linked lists, we use a helper function called mergeTwoLists.
- This function takes two pointers, p1 and p2, each pointing to the head of a sorted list.
- We create a new dummy node, ans, to build the merged list.
- While both p1 and p2 are not null, we compare the values at their current positions.
- We append the node with the smaller value to the merged list and advance the respective pointer.
- We continue this process until one of the lists becomes null.
- Finally, we attach the remaining nodes (if any) from the non-null list to the merged list.
Return the Result:
- After pairwise merging, we're left with one merged list in the array.
- We return the head of this merged list as our final result.

Code:


    ListNode* mergeTwoLists(ListNode* p1, ListNode* p2){
        ListNode* ans = new ListNode();
        ListNode* temp = ans;

        while(p1 && p2){
            if(p1->val < p2->val){
                temp->next = p1;
                p1 = p1->next;
            }
            else{
                temp->next= p2;
                p2 = p2->next;
            }
            temp = temp->next;
        }

        if(p1) temp->next = p1;
        else temp->next = p2;

        return ans->next;

    }
   ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return nullptr;
    if (n == 1) return lists[0];

    while (n > 1) {
        int k = (n + 1) / 2;
        for (int i = 0; i < n / 2; ++i) {
            lists[i] = mergeTwoLists(lists[i], lists[i + k]);
        }
        n = k;
    }

    return lists[0];
}

Let's analyze the time and space complexity of our solution:

Time Complexity: The time complexity depends on the number of nodes in all the linked lists. During each pairwise merge, we traverse all the nodes exactly once. Since we perform log₂(k) iterations (where k is the number of linked lists), the total time complexity is O(N⋅log(k)), where N is the total number of nodes.
Space Complexity: The space complexity is O(1) for variables used in the algorithm, and we don't use any additional data structures apart from the input and output. Therefore, the space complexity is O(1).

DAY 103 - Copy List with Random Pointer

Nayan Pahuja — Thu, 14 Sep 2023 12:18:52 +0000

Hey Guys!, Welcome to DAY 103 and we are continuing on our journey to master linked list. Today we are back with an interesting question. So Let's get right down to it.

Question: Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list.

Examples:

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Question Breakdown:

Ok so despite the lengthy the problem is quite easy to understand.
The description is asking us to make an exact to exact copy of the given linked list.
So what's the catch? The catch is that we have to create a copy of new node and allocate it in a new memory(space), we can't use the old linked list or have any of our nodes point back to it's nodes.
To add to our difficulty, they have given us a random pointer which points to any node in the linked list.

Intuition:

Ok so this seems easy, we can just do a loop and make new Nodes and pointers for every and move ahead?.
Yeah but we also need to deal with random pointers pointing at nodes that have not existed yet or been created yet.
Look in example 1:, if we make a copy of it line by line our 2nd node points to last node, but if we haven't reached last node how will create a pointer to it.
Well How about we forget pointing at all and first make all the nodes. If we don't assign pointer to it? how will we move, well we can use a map to link old list and new list.
Using a map we can link them and after we have created nodes , now any of our node's next or random pointer's will point to a node that actually exists in memory.

Approach:

First Pass: Creating New Nodes
- We start by iterating through the original list using a temporary pointer, temp.
- While traversing, we create a new node for each node in the original list and assign its val with the same value as the original node.
- We also store a mapping between the original node and the new node in an unordered map (nodes) for the creation of random pointers later.
Second Pass: Setting next and random Pointers
- We reset temp to the head of the original list.
- While traversing the original list again, we set the next and random pointers for each new node.
- For the next pointer, we look up the mapping in the nodes map to find the corresponding new node.
- For the random pointer, we do the same: look up the mapping to find the corresponding new node.
Returning the Result
- Finally, we return the head of the new list, which is stored in nodes[head].

Code:


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> nodes; //use to store link to old nodes and new nodes

        Node* temp = head; //temporary pointer to fill nodes

        while(temp){
            nodes[temp] = new Node(temp->val); //make copy of node and attach to nodes
            temp = temp->next;

        }
        temp = head; //reinitialize the pointer so that we can traverse again
        while(temp){
            Node* newNode = nodes[temp];
            newNode->next = nodes[temp->next];
            newNode->random = nodes[temp->random];
            temp = temp->next;
        }

        return nodes[head];
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of this solution:

Time Complexity: This solution makes two passes through the entire linked list. Therefore, the time complexity is O(N), where N is the number of nodes in the linked list.
Space Complexity: The space complexity is O(N) as well. We use additional space to store the mapping between original nodes and new nodes in the nodes hash map. The space required for the new linked list is also O(N) as we create a new node for each node in the original list.

DAY 102 - 2130. Maximum Twin Sum of a Linked List

Nayan Pahuja — Wed, 13 Sep 2023 12:22:36 +0000

Hello People!. Continuing our challenge until we break it , we continue on our path to learn linked list and solve it's leetcode problems. Today we are going to do a very easy problem and the intuition behind this can be sometimes hard to catch, so let's start.

Question: 2130. Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:

Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.

Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4. Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Problem Breakdown:

We are given a singly linked list of even length each having value from 0 to 10^5.
We are also given a pair relation, to simplify the relation it's the first node from the start and last node. They make a pair and we move ahead from start to next node and we move back from last node to our second last node, sequentially every such two nodes form a pair.
Okay so, if anyone has done a little bit of coding questions, this is pretty easy, We can simply take a vector to store the values and use a while loop to traverse from both ends using two pointers and find the maximum.
Yes but in this approach we will be using O(N) extra space, the challenge lies in solving this without using extra space.

So how do we do it? Let's head down to approach.

Intuition:

So the challenge is we can only move forward in our linked list.
If we could move back we could solve this right, obviously we can't make this into a doubly linked list so how do we move back.
Let's first identify which nodes do we need, L0 & LN , L1 & LN-1 , L2 & LN-2 and so on...
If we carefully see our mid pointer will have it's next node as it's pair.
If we can somehow travel in reverse after our mid, we will be able to get the solution.
Let's try doing this exactly, we divide our linked list into two parts, one is our left part and one is our right part.
When we reverse a linked list the last node is our head.
After we reverse it, we now have a pointer to last node and we can move forward.

Continuing on our intuition let's write the approach:

Approach:

Reverse the Right Half of the List:
- First, we identify the middle of the linked list using Floyd's Tortoise and Hare algorithm. We do this by having two pointers, slow and fast, traverse the list at different speeds. When they meet, slow points to the middle node.
- Next, the right half of the linked list is reversed. Reversing the list makes it easier to calculate the maximum pair sum.

In case you don't know this approach, check out my article on it : Floyd's tortoise and hare algorithm

Find the Maximum Pair Sum:
- With the right half of the list reversed, we initialize two pointers, p1 and p2, at the heads of the original and reversed lists, respectively.
- As the pointers traverse the lists, the maximum sum of pairs is calculated. We do this by by summing the values of nodes pointed to by p1 and p2 and updating the maximum sum (maxi) if we encounter larger sum.
- We continue the process until both pointers reach the end of their respective lists.
Return the Maximum Sum:
- The maximum pair sum (maxi) is the result of the problem and hence we return it.

Code:


/**
 * 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* reverseList(ListNode* head){
    if(!head) return head;

    ListNode* prev = NULL;
    ListNode* cur = head;
    ListNode* nex = cur->next;

    while(cur){
        cur->next = prev;
        prev = cur;
        cur = nex;
        if(nex) nex = nex->next;
    }
    return prev;
}

    int pairSum(ListNode* head) {

        //find the middle node of the list using floyd's tortoise and hare
    ListNode* slow = head;
    ListNode* fast = head;

    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast){
            break;
        }
    }

    //slow points to middle of the list
    //cut the list from middle


    //reverse the right list
    ListNode* p1 = head;
    ListNode* p2 = reverseList(slow);

    int maxi = INT_MIN;
    while(p2){
        maxi = max(maxi,p1->val + p2->val);
        p1 = p1->next;
        p2 = p2->next;
    }
    return maxi;
    }
};

Time and Space Complexity

Now, let's analyze the time and space complexity of this solution:

Time Complexity: We traverse the entire linked list twice. The first traversal finds the middle of the list, and the second traversal calculates the maximum pair sum. Therefore, the time complexity is O(N), where N is the number of nodes in the linked list.
Space Complexity: We use a constant amount of extra space for variables. No additional data structures or memory allocation is required, resulting in a space complexity of O(1).

DAY 101 - 61. Rotate List

Nayan Pahuja — Tue, 12 Sep 2023 05:42:26 +0000

Hey Everyone!, a bit change of plans, I will be continuing this series until I accidentally break it.

Today we are going to do another linked list question, which is quite encountered in arrays as well is rotate the linked list.

Question: Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Understanding the Problem

Before we dive into the code, let's break down the problem and understand its requirements:

We're given a linked list head where each node contains a value.
We need to perform operations in the such that list should be rotated to the right by k positions.
We need to return the head of the new linked list after the rotation.

Intuition:

We've encountered such type of problems in arrays first and truth be told, we are not going to change our approach much here.
We know that if k > length of the list we need it's modulus because it's just one length wrapped around + rotations. -We need to find out what will be the end in our rotated list.
Our len - k will give us the ending node of the final list, so now we know what should be null.
We just make the node next to it head and our ending point null after making it a circular list.
Let's write approach for better understanding.

The Approach

Base Cases: First, we handle the base cases where no rotation is needed or where the input linked list is empty or contains only one node. In these cases, we directly return the head since no rotation is required.
Calculate the Length: We need to determine the length of the linked list to understand how many positions to rotate. We traverse the linked list once and count the number of nodes to find the length.
Make the List Circular: Since the rotation should wrap around, we connect the last node to the head, effectively making it circular.
Calculate the New Head: To find the new head of the rotated list, we need to locate the node that will become the first node in the rotated list. This node is located at a position len - k, where len is the length of the list and k is the number of positions to rotate.
Break the Circular List: After determining the new head, we need to break the circular list. We set the next of the node at position len - k to nullptr.
Return the Result: Finally, we return the new head, which represents the rotated linked list.

Code:

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr || k == 0){
            return head;
        }

        //only rotate by len % k
        int len = 1;
        ListNode* temp = head;
        while(temp->next){
            temp = temp->next;
            len++;
        }

        //we got the length now;
        //make it circular
        temp->next = head;
        k = k % len;
        int end = len - k;

        while(end--){
            temp = temp->next;

        }

        head = temp->next;
        temp->next = nullptr;


        return head;

    }
};

Complexity Analysis:

Time Complexity: The algorithm makes a single pass through the linked list to calculate its length, so its time complexity is O(N), where N is the number of nodes in the linked list.
Space Complexity: The algorithm uses a constant amount of extra space for variables, so the space complexity is O(1).

DAY 100 - 1282. Group the People Given the Group Size They Belong To

Nayan Pahuja — Mon, 11 Sep 2023 07:46:02 +0000

Hey Guys! Welcome to the 100th Day in our 100DaysOfCodeChallenge.
Before starting today's question, I would like to thank anyone who has spared time to read what I've written over the course of 100 days and anyone who reads this into the future. I won't say much but the journey has been amazing and I recommend everyone to take this challenge at least once. It's a whole another feeling of it's own.

I am going to take a quick break of a week or something probably less and I will be back but I will be writing more freely now and will try other things than Data Structures and Algorithm Articles.

Let's get back to our work, today we are going to sovle today's daily leetcode question.

Question: 1282. Group the People Given the Group Size They Belong To

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

Return a list of groups such that each person i is in a group of size groupSizes[i].

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers,return any of them. It is guaranteed that there will be at least one valid solution for the given input.

Example:

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

Understanding the Problem

Before we delve into the code, let's gain a clear understanding of the problem:

We're given an array groupSizes where groupSizes[i] represents the group size that the i-th person belongs to.
Our task is to group people together based on their group sizes while ensuring that each group contains exactly groupSizes[i] people.
The order of people within each group does not matter, but the order of groups in the result matters.
From these observations it's clear to us we need to somehow maintain which indexed person it is, his groupSize and he must go into that groupSize.

Intuiton:

By breaking down the question we realize we have to keep tracks of two things:
First: The groupSizes of the i'th index denote the groupSize it must be in.
Second: We also need to keep track of other members of that specific group size.
We are related by two things, the key (size of the group) and it's members(indexes of that specific group size).
We can simply use an unordered_map<int,vector<int>> here as it will help us keep track of both the things. Our map will store a vector containing members corresponding to our keys.
But if we store all the members they might be greater than the groupSize and we might need to make more groups for it.

Let's head down to the approach we used to solve this:

The Approach

To solve this problem efficiently, we can use a systematic approach. Here's the intuition behind the approach:

Initialize a Data Structure: We start by initializing two data structures: a vector of vectors called result to store the final answer and an unordered map called mp to help us organize the people based on their group sizes.
Iterate Through the Input Array: We traverse the groupSizes array using a loop. In each iteration, we perform the following steps:

Extract the key, which represents the group size for the current person.
Add the person's index (representing a member) to the corresponding group in our mp map.
Check if the group is now full, meaning it contains exactly key people. If so, we move all the members of that group from mp to our result vector. This ensures that we have created a complete group, and we can remove the group size from mp.

Return the Result: Finally, we return the result vector, which contains all the groups of people based on their group sizes.

Code:


class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> result;
        unordered_map<int,vector<int>> mp;

        for(int i = 0; i < groupSizes.size(); ++i){
            int key = groupSizes[i]; //this is the groupSize for that index

            mp[key].push_back(i); //push the members of that specific group

            if (mp[key].size() == key) { // group is full so push that into our answer
                result.push_back(mp[key]);
                mp.erase(key);
            }

        }



        return result;
    }
};

Complexity Analysis:

Time Complexity: We make a single pass through the groupSizes array, so its time complexity is O(N), where N is the length of the input array and our insertion and deletion in unordered_map is O(1). So our overall time complexity is O(N).
Space Complexity: We use two data structures, the result vector and the mp unordered map. The space required for result is proportional to the number of groups and can be as large as N/2 in the worst case. The space used by mp is also proportional to the number of groups. Therefore, the space complexity is O(N).