Unlocking the Hidden Patterns: The Wonders of Binomial Coefficients and Pascal's Triangle

Understanding the Binomial Coefficient:

        Imagine you have a group of 5 friends (let's name them A, B, C, D, and E), and you want to select 3 of them to form a team for a game. The binomial coefficient $\left(\genfrac{}{}{0px}{}{5}{3}\right)$ tells you how many different teams of 3 you can form from the 5 friends.

Breaking Down the Formula:

The formula for the binomial coefficient is $\left(\genfrac{}{}{0px}{}{�}{�}\right)=\frac{�!}{�!(�-�)!}$. Let's break it down using our example where $�=5$ and $�=3$:

1. 1. Factorials: The "!" symbol stands for factorial. For any positive integer $�$, $�!$ (x factorial) is the product of all positive integers up to $�$. For example, $5!=5\times 4\times 3\times 2\times 1=120$.

2. 2. Applying the Formula: To find $\left(\genfrac{}{}{0px}{}{5}{3}\right)$, we plug our numbers into the formula:

   $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{5!}{3!(5-3)!}=\frac{5!}{3!2!}$

   Calculating each factorial:

   
   
   • $5!=120$
   • $3!=6$
   • $2!=2$

   So, $\left(\genfrac{}{}{0px}{}{5}{3}\right)=\frac{120}{6\times 2}=\frac{120}{12}=10$.
   

   This means there are 10 different ways to choose 3 friends out of 5.

3. Why Does the Formula Work?

4. 
   

5. 1. Starting with Permutations: Initially, if we were to line up 3 of your friends out of 5, not just choose them, we'd have to consider the permutations (different arrangements). For the first friend, you have 5 choices, for the second, you have 4 (since one friend is already chosen), and for the third, 3 choices left. So, for permutations, you multiply these:

1. $5\times 4\times 3=60$.

2. 2. Adjusting for Order Not Mattering: The 60 permutations include different orders of the same 3 friends (like ABC, ACB, BAC...). But in our case, the order doesn't matter; ABC is the same team as BAC. Each group of 3 friends can be arranged in $3!=6$ ways (3 options for the first position, 2 for the second, and 1 for the last), so we've counted each group 6 times in our 60 permutations.

3. 
   

4. 3. Getting to Combinations: To correct for this and count each unique group once, we divide the number of permutations by the number of ways to arrange 3 friends:

5. $\frac{60}{6}=10$. This matches our calculation using the binomial coefficient formula, showing that there are 10 unique ways to choose 3 friends out of 5.

6. Conclusion:

             The binomial coefficient formula $\left(\genfrac{}{}{0px}{}{�}{�}\right)$ gives us a way to calculate the number of unique groups (combinations) of $�$ items we can choose from a larger set of $�$ items, without caring about the order of selection. It corrects for the overcounting of arrangements (permutations) by dividing by the factorial of the group size $�!$, ensuring each unique group is only counted once.

Now lets gets into the most interesting part. The pascals triangle and creating it with Binomial Coefficients.     

 

First lets start with writing a small program to print pascals matrix to the nth row.

Idea behind this program is pretty simple List<List>  basically represents Column<Rows> or a matrix.  

  Each rows first and last value will be one that we hard code. Then iterate over numRows and construct each rows. One small thing to notice here is the inner for loop it has to run from 1 to < less than rowNum. Basically it runs 1, 2, 3 times from the 2nd  row. So basically rowNum-1 times it runs, basically skipping for first two rows.

    Lets move forward to  to understand the relation between binomial coefficient and the pascals triangle. If you look closely you can find something really interesting. Below is the representation of of pascals triangle 

If you did not catch this yet see the below which will unlock the hidden pattern of the relation between binomial coefficient and pascals triangle

with this we now understood the relation between pascals triangle and binomial coefficient. Great now for a very dumb person like me can easily understand what Striver is saying in his video. Now the below program makes a lot of sense. Check the below program which will show you how to calculate the value in a particular position of the pascals triangle.

If you reached this far of the blog then great you are upto something special in your life. Stay tuned for the next blog

Designing a Browser History Feature

Objective

The goal is to create a class capable of handling browser history operations efficiently. This includes:

• Initializing the browser with a specified homepage.
• Navigating to new URLs (visiting pages).
• Enabling backward and forward navigation through the history.

Key Components

• Constructor: Initializes the browser with a homepage.
• Visit(URL): Navigates to a new URL and updates the current position in the history.
• Back(steps): Moves back a specified number of steps in history and returns the current URL.
• Forward(steps): Moves forward a specified number of steps in history and returns the current URL.

Implementation

We will use a doubly linked list to manage the history of visited URLs, allowing for efficient navigation both backward and forward.

class BrowserHistory {
    class Node {
        String url;
        Node prev, next;

        public Node(String url) {
            this.url = url;
        }
    }

    private Node current;

    public BrowserHistory(String homepage) {
        current = new Node(homepage);
    }

    public void visit(String url) {
        Node newNode = new Node(url);
        current.next = newNode;
        newNode.prev = current;
        current = newNode; // Move forward to the new page
    }

    public String back(int steps) {
        while (current.prev != null && steps-- > 0) {
            current = current.prev;
        }
        return current.url;
    }

    public String forward(int steps) {
        while (current.next != null && steps-- > 0) {
            current = current.next;
        }
        return current.url;
    }
}

Example Usage

BrowserHistory browserHistory = new BrowserHistory("takeuforward.org");
browserHistory.visit("google.com"); // User visits 'google.com'.
browserHistory.visit("instagram.com"); // User then visits 'instagram.com'.
browserHistory.back(1); // User goes back one step to 'google.com'.
browserHistory.back(1); // User goes back another step to 'takeuforward.org'.
browserHistory.forward(1); // User moves forward to 'google.com' again.
browserHistory.visit("takeuforward.org"); // User visits 'takeuforward.org', overwriting forward history.
browserHistory.forward(2); // No forward history, remains on 'takeuforward.org'.
browserHistory.back(2); // User goes back to 'google.com'.
browserHistory.back(7); // Attempts to go back 7 steps but only goes back to the homepage.

Complexity Analysis

• Constructor: O(1) - Only involves initializing a single node.
• Visit(URL): O(1) - Adding a new node to a doubly linked list is a constant time operation.
• Back(steps) and Forward(steps): O(steps) - Proportional to the number of steps taken, due to traversal through the linked list.

This design mirrors the functionality of real web browsers, offering an intuitive navigation experience while ensuring operations are performed efficiently.

An early morning adventure

On the early morning of February 1st, I decided to tackle a problem from the Striver's SDE sheet.

I came across an intriguing challenge titled "Set Matrix Zeroes".

Here's how I approached it:

Initially, I attempted a brute force method. The usual strategy of iterating through a matrix and setting rows and columns to zero has a drawback: it can lead to the loss of the matrix's original state, potentially zeroing out the entire matrix, which isn't the desired outcome. To avoid this, my approach involved marking the rows and columns that intersect at a zero element with a temporary value of -1. This way, the matrix's original elements remain unchanged until the final step, where a second pass converts all -1 values back to zeros.

The main drawback of this method is its inefficiency, with a time complexity that could be roughly estimated as (O((m times n)^2)), due to the need for multiple iterations over the matrix.

Seeking improvement, I explored an optimal solution that builds upon the brute force idea but introduces two marker arrays, one for rows and another for columns. As we scan the original matrix, we use these arrays to mark any row or column containing a zero. A subsequent iteration through the matrix then uses these markers to set the corresponding elements to zero. This refined approach reduces the number of iterations, achieving a time complexity of (O(2 times m times n)).

Despite the improvement, I wondered if there was an even better solution. Recalling that I had previously solved this problem on LeetCode under the title "Set Matrix Zeroes" (you can find the problem [here](https://leetcode.com/problems/set-matrix-zeroes/)), I revisited my submission. To my surprise, I had employed a different, more efficient strategy in my past solution, which can be viewed [here](https://leetcode.com/problems/set-matrix-zeroes/submissions/1004912402/).

The best solution I found leverages the first row and first column of the matrix as marker arrays, eliminating the need for additional space. A special variable is used to determine whether the first row or column should be entirely zeroed. This approach requires careful iteration from the second row and column onwards, with a final pass to address the first row and column as needed.

For those interested in the solutions, they are available on my GitHub repository at [this link](https://github.com/mathewjustin/2024-DsAndAlgo/tree/main/src/main/java/com/codepower/striver/arrays).

Thank you for taking the time to read this if you've made it this far.

Justin

An engineers view to religion

KEEP ONE HAND DISTANCE!

Moving from a wonderful organiztion !

Cycle travelled all the way from Bangalore to Kannan devan hills, Idukki. ;) 

A wonderful journey of last 3 years has come to an end. Moved out of MBRDI / DTICI ( Daimler Trucks Innovation Center India)

Automate fetch upstream using github actions

        I like to fork interesting github repositories and experiment with it. Those who do this actively might have faced the problem of upstream sync, where we need to sync our repository with the upstream repository. Imagine you forked a repository contains some articles which are being updated everyday, you will like them to have it synced everyday. I do ;) 

  Github introduced a feature called fetch upstream this year to solve this issue. But in this case you need to click on the fetch upstream button by yourself, this article is for the lazy ones who want it to be done automatically. 

   In this blog we are about to learn how to automate upstream fetch of any repository you cloned. We are using Github actions to do this. The below is the yaml configuration for my github action

   

Here you can see the cron is set to run at midnight, also as you might have already noticed i have created a simple bat file to be excecuted, you can see it below. Next step is to configure a github action with the yml file we created. Go to Actions tab

Click on New Workflow-> Skip this and set up workflow yourself.

Here you can select the yml file you created under your repository. Once you set it it up your fork will automatically sync every night. 

You can see this example live on my github repository :  every-programmer-should-know 

Cheap Fast Good

 

You can make a great software but you have to choose 2 out of this above 3. There is no way to get around!

Python linked List implementation

 

class Node:
     def __init__(self, data):
         self.data=data
         self.nextNode=None



class LinkedLIst:

    def __init__(self):
        self.head = None
        self.numberOFNodes=0
     # Here we get o(1) constant running time complexity for insertion.
    def insert_start(self,data):

        self.numberOFNodes=self.numberOFNodes+1
        new_node = Node(data)

        if not self.head:
            self.head=new_node
        else:
            new_node.nextNode=self.head
            self.head = new_node
 #Linear running time o(n)
    def insert_end(self,data):
        self.numberOFNodes=self.numberOFNodes+1
        new_node=Node(data)

        actual_node=self.head

        while actual_node.nextNode is not None:
            actual_node=actual_node.nextNode

        actual_node.nextNode=new_node

    def size_of_list(self):

        actual_node = self.head

        while actual_node is not None:
            print(actual_node)
            actual_node=actual_node.nextNode

    def traverse(self):
        actual_node=self.head

        while actual_node is not None:
            print(actual_node.data)
            actual_node=actual_node.nextNode

    def deleteAtHead(self):

        self.head=self.head.nextNode
        self.numberOFNodes=self.numberOFNodes-1

    def deleteAtTail(self):

        actual_node = self.head

        while actual_node.nextNode.nextNode is not None:
            actual_node=actual_node.nextNode

        actual_node.nextNode=None
        self.numberOFNodes=self.numberOFNodes-1



linked_list=LinkedLIst()
linked_list.insert_start(4)
linked_list.insert_start(3)
linked_list.insert_start('A String type')
linked_list.insert_start(1.232)
linked_list.insert_end(12.232)
linked_list.traverse()

print('Deleting at the front')
linked_list.deleteAtHead()
linked_list.traverse()

print('Delete at the last position')
linked_list.deleteAtTail()
linked_list.traverse()