DEV Community: Sourav

Retrieve Vaccine Slots in your locality (Python Web-Scrapping)

Sourav — Sun, 23 May 2021 15:53:27 +0000

I know it is hard to get a vaccine slot. I have been trying to get a slot for the last two weeks; still have not got it. Therefore I decided to make a python script that will notify me about the vaccination slots.

For this, we will use the APIs provided by our Indian Government and scrap the page. If you try to do a lot of requests to the server, your IP address may be blocked. BEWARE!!!!!!!!!!!

What is Web Scraping

Web scraping is the process of using bots to extract content and data from a website.

Cowin-API

You can check the APIs from this page. (Link)

Let’s have a look at the response for the network which we are going to make. We have to create a model to extract that information.

Demo API call: https://cdn-api.co-vin.in/api/v2/appointment/sessions/public/calendarByPin?pincode=110001&date=23-05-2021

We have to find the available_capacity field for each session in each centre.

Coding part

First, install the requests and plyer library.

pip install requests and pip install plyer

Import these libraries, they will be needed. requests is used to make HTTP requests, plyer is used to send desktop notifications. time and datetime are used to handle date-time related things, need to convert them into appropriate formats.

import requests
import time
from datetime import datetime,timedelta
from plyer import notification

Now, we will define some parameters which will be used for searching. You have to enter the age, pin codes and the number of days you want to search for. The API allows us to search for availability for the next 7 days.

user_age = 55
pincodes=["782411","782410"]
num_days = 6

We also have to convert to the dates into a suitable format so that we can make the API call. We extract today’s date from datetime and convert the next num_days accordingly.

actual = datetime.today()
list_format = [actual + timedelta(days=i) for i in range(num_days)]
actual_dates = [i.strftime("%d-%m-%Y") for i in list_format]

Now comes the main part. We have to search for all the pincodes for all the given dates. Also, the search is needed to be done for all the centres for all the sessions. If any conditions are satisfied, then we will print that result. That result will be sent as a notification to the desktop. After the search is completed, we will wait for 5 minutes (use sleep function) and continue searching again.

while(True) :
    availbleCenters = 0

    #We have to search for all pincodes for all the given dates
    for pincode in pincodes:
        for date in actual_dates:
            #The API to hit for our operation
            URL = f"https://cdn-api.co-vin.in/api/v2/appointment/sessions/public/calendarByPin?pincode={pincode}&date={date}"
            header = {
                'User-Agent': 'Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.76 Safari/537.36'}

            result = requests.get(URL, headers=header)
            #If the response is 200 then proceed
            if result.ok:
                response_json = result.json()
                #We have to search for available capacity in each session for each center
                for center in response_json['centers']:
                    for session in center['sessions']:
                        #If the condition is satisfied like the available capacity is not zero and age limit is also satisfied then print them
                        if (session['available_capacity']>0 and session['min_age_limit']<=user_age and session["date"] == date ):
                            availbleCenters = availbleCenters+1
                            print('Center Name : ' , center['name'])
                            print('Available slots : ' , session['available_capacity'])
                            print('Pincode : ' , pincode)
                            print('Vaccine Name : ' , session['vaccine'])
                            print('Date : ', session['date'])
                            print('----------------------------------')

                            centerName = center['name']
                            availbleSlots = session['available_capacity']
                            dateOfSlot = session['date']
                            vaccineName = session['vaccine']
                            #plyer is used here to notify people in desktop.
                            notification.notify(
                                title="Vaccine Slots Availble",
                                # the body of the notification
                                message=f"Center Name : {centerName} \n Availble slots : {availbleSlots} \n Vaccine Name : {vaccineName} \n Date : {dateOfSlot}",
                                #You can add a icon here also in the .ico format
                                # the notification stays for 5sec
                                timeout=5
                            )


            else:
                print("No Response")

    if availbleCenters==0:
        print("No availble slots in these areas...")
        notification.notify(
            title="No Vaccine Slots are available",
            # the body of the notification
            message="Sorry, there is no available slot in your area",
            # You can add a icon here also in the .ico format
            # the notification stays for 5sec
            timeout=5
        )
    else:
        print(f"Hurray. Found {availbleCenters} results...")
    #The process will resume after 300 seconds. That means we will make the APi call again after 5 minutes.
    time.sleep(300)
    print("Waited for 5 minutes. Start searching again")

After you run this script, you will receive notifications every 5 minutes if there is any available slot in your area. Hurray!!!!! We have completed the work.

The notification will be shown like this.

The results will also be printed on the console just like this.

If there is no available slot in those pin codes, you will receive “NO RESPONSE” on the console. You will receive a notification stating no vaccine slots available. You can easily tweak the time for notifications.pincodes and days. Go ahead and play with it.

The complete work can be found here.

sksaikia / Cowin-Notifier

Cowin-Notifier

This is a python script which can notify you about vaccination available slots. It uses the API provided by CoWIN and fetches available slots for vaccination. You can input your pincodes(multiple) and number of days you want to fetch and it will notify you about the slots. Pincode, number of days and search time can be changed from the script.

Full Setup Guide

You have to install multiple packages for it.

Install requests (Used for make HTTP requests)
```
pip install requests
```
Install Plyer (Used for sending desktop notifications)
```
pip install plyer 
```

You can find the full tutorial here.

View on GitHub

MayLeetCoding Challenge 2021 — Day 4: Non-decreasing Array

Sourav — Tue, 04 May 2021 13:37:21 +0000

Today is May the 4th. Happy Star Wars Day everyone.

Let’s solve some Leetcode problems today. Today we will solve the 4th problem of the May LeetCoding Challenge 2021.

Problem Statement

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

**Input:** nums = [4,2,3]
**Output:** true
**Explanation:** You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

**Input:** nums = [4,2,1]
**Output:** false
**Explanation:** You can't get a non-decreasing array by modify at most one element.

Solution

We are going to solve this problem greedily. We can modify at array at max 1 time so that it becomes a non-decreasing array.

To achieve that, we have to take care of few things.

When modifying the number at index i-1 , we need to consider elements at i-2 and i -th index.
Need to make sure that the array satisfies the conditions even after modifications are made.

Correction can be made in either of two ways:

Make the previous number smaller or equal to the current number
Make the current number equal to the previous number

We can do the first as long as the number at position i-2is equal or lower than the current element(index i),if i-2is valid. If we can’t then go for the second condition. We give priority to the first case.

Check the code below.

Time complexity:O(n)

Space complexity:O(1)

Check the whole repository for more leetcode solutions.
sksaikia/LeetCode

MayLeetCoding Challenge 2021 — Day 3: Minimum Operations to Make Array Equal

Sourav — Tue, 04 May 2021 13:35:00 +0000

Today, we will solve the 3rd problem of the May LeetCoding Challenge 2021.

Problem Statement

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

**Input:** nums = [1,2,3,4]
**Output:** [1,3,6,10]
**Explanation:** Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

**Input:** nums = [1,1,1,1,1]
**Output:** [1,2,3,4,5]
**Explanation:** Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

**Input:** nums = [3,1,2,10,1]
**Output:** [3,4,6,16,17]

Solution

This is a pretty easy problem. Here we have to find the running sum of an array. That means, for index i we have to find the sum of all elements from 0 to i-1 . It can be done by using sum variable to store the summation of each element index by index.

The code is given below.

Time complexity: O(n)

Space complexity: O(n)

where n is the size of the array

For the whole repository click the link below.

sksaikia / LeetCode

LeetCode

I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.

Follow me on medium - https://sourav-saikia.medium.com
Follow me on dev.to - https://dev.to/sksaikia
Follow me on twitter - https://twitter.com/sourav__saikia
Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37
Design Authentication Manager	1797	https://sourav-saikia.medium.com/leetcode-1797-design-authentication-manager-biweekly-contest-48-8ef4d82a220d

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820

…

View on GitHub

April LeetCoding Challenge 2021 — Day 6: Minimum Operations to Make Array Equal

Sourav — Tue, 06 Apr 2021 20:20:08 +0000

Today, we will solve the 6th problem of the April LeetCoding Challenge 2021.

Problem Statement

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arry. The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

**Input:** n = 3
**Output:** 2
**Explanation:** arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2:

**Input:** n = 6
**Output:** 9

Solution

This is a basic problem. Here we have to make all the elements of the array equal by a particular operation. We have to find the minimum number of steps to make the array elements equal.

To do this task in minimum steps, we can convert the elements into their mean value.

According to the question, the elements at i-th index is (2*i)+1 . Therefore the mean of these elements will be n ,which is given in the question.

The code is given below.

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37
Design Authentication Manager	1797	https://sourav-saikia.medium.com/leetcode-1797-design-authentication-manager-biweekly-contest-48-8ef4d82a220d

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820

…

View on GitHub

April LeetCoding Challenge 2021 — Day 1: Palindrome Linked List

Sourav — Thu, 01 Apr 2021 20:33:48 +0000

From today, we will start doing the April LeetCoding Challenge. You can check the March LeetCoding Challenge problems on my profile.

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

**Input:** head = [1,2,2,1]
**Output:** true

Example 2:

**Input:** head = [1,2]
**Output:** false

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution

In this problem, we have to find whether a given LinkedList is palindrome or not. I hope you know what a Palindrome is. (Check here)

We are going to discuss two approaches to this problem.

Approach 1: Using ArrayList: The basic idea behind this approach is to store all the node values in an ArrayList. After that, we traverse the list for start and end, and keep comparing the values at start index and end index. If they are equal then increase start index and decrease end index. If two values are not the same, then we return false(the LinkedList is not a palindrome).

Time Complexity:O(n), for traversing the LinkedList

Space Complexity:O(n), using ArrayList for storing the node values

Approach 2: In this method, we will use LinkedList manipulations.

If the length of the LinkedList is even :

Find the middle point of the LinkedList.
Reverse the second half.
Compare the reverse list to the first half of the list, if all the values are equal return true else return false

If the length of the LinkedList is odd:

Find the middle point of the LinkedList. As the length is odd, the middle point will be between the first half and second half of the LinkedList.
Now reverse the second half of the Linked List
Compare the reverse list to the first half of the list, if all the values are equal return true else return false

The code is given below.

Time Complexity:O(n), for traversing the LinkedList

Space Complexity:O(1), No additional space is used

The code can be found here

sksaikia / LeetCode

Leetcode solutions in java. Problems are divided by problem number (i.e 1-100, 101-200 etc.) . This repository contains more than 300 problem solutions

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37
Design Authentication Manager	1797	https://sourav-saikia.medium.com/leetcode-1797-design-authentication-manager-biweekly-contest-48-8ef4d82a220d

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820

…

View on GitHub

March LeetCoding Challenge 2021 — Day 19: Keys and Rooms

Sourav — Sat, 20 Mar 2021 07:46:17 +0000

Today, we will solve the 19th problem of the March LeetCoding Challenge.

Problem Statement

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

**Input: **[[1],[2],[3],[]]
**Output: **true
**Explanation:  **
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

**Input: **[[1,3],[3,0,1],[2],[0]]
**Output: **false
**Explanation: **We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

Solution

In this problem, we have to find whether we can visit all the rooms. Initially, the 0-th room is opened, and at every index, we have the keys to go to other rooms. So, we can visualize this problem as a graph-based problem.

Once we enter the 0-th room, we will check for keys in that room. Once we find a key, we directly move to that room and repeat the process. We keep the count of visited rooms in a HashSet. If the size of the HashSet is equal to the number of rooms, we return true else false. We are using breath-first-search to solve this problem.

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check out my other posts on March LeetCoding Challenge 2021.

March LeetCoding Challenge 2021 — Day 18: Wiggle Subsequence

Sourav — Thu, 18 Mar 2021 15:24:31 +0000

Today, we will solve the 18th problem of the March LeetCoding Challenge.

Problem Statement

Given an integer array nums, return the length of the longest **wiggle sequence**.

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.
In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

**Input:** nums = [1,7,4,9,2,5]
**Output:** 6
**Explanation:** The entire sequence is a wiggle sequence.

Example 2:

**Input:** nums = [1,17,5,10,13,15,10,5,16,8]
**Output:** 7
**Explanation:** There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Example 3:

**Input:** nums = [1,2,3,4,5,6,7,8,9]
**Output:** 2

Solution

With this problem, we have to find the longest wiggle subsequence. Wiggle subsequence means that the difference between successive elements is alternating between positive and negative.

For solving this problem we will use dynamic programming. We will go through two approaches, one with O(n²) and another one with O(n).

Approach 1: We will use two arrays up and down. up array refers to the length of the longest wiggle subsequence where the ending element is a rising wiggle. Similarly, the down array refers to the length of the longest wiggle subsequence where the ending element is a falling wiggle.

We will update the up[i] when we find a rising wiggle at index i. But there is a catch. We have to consider the previous wiggle subsequence which ends with a falling wiggle (because we need to make sure that the subsequence overall is wiggle). We follow the same in the case of down[i].

The code is given below.

Here we are using two loops. To check the longest wiggle subsequence at index i , we check for each element from 0 to i-1.

Time complexity: O(n²), n is the length of the array

Space complexity: O(n), n is the length of the array

Approach 2: With this approach, we only use a single loop and two arrays named up and down. Here, we have 3 cases.

When nums[i]>nums[i-1]:it means it wiggles up. So the element before it must be in down position. Therefore, up[i] = down[i-1]+1 and down[i] will be same as down[i-1].
When nums[i]<nums[i-1]: it means the wiggles down, the element before it must be in up position. Therefore down[i] = 1+up[i-1] and up[i] will be same as up[i-1].
If nums[i]=nums[i-1],then up[i] will be up[i-1] and down[i] will be down[i-1].

The code is given below.

Time complexity: O(n), n is the length of the array

Space complexity: O(n), n is the length of the array

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check out my other posts on March LeetCoding Challenge 2021.

March LeetCoding Challenge 2021 — Day 15: Encode and Decode TinyURL

Sourav — Wed, 17 Mar 2021 06:15:01 +0000

Today, we will solve the 15th problem of the March LeetCoding Challenge.

Problem Statement

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Solution

In this problem, we have to design an URL shortening service to encode and decode URLs. Therefore for a given longURL we should be able to get the shortURL with encode method and vice versa in the decode method.

So we can use the in-built hashcode method, because that will generate a unique value for any given string. We can store the hashcode value in a HashMap and retrieve it in the decode method.

The code is given below.

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check out my other posts on March LeetCoding Challenge 2021.

March LeetCoding Challenge 2021 — Day 14: Swapping Nodes in a Linked List

Sourav — Wed, 17 Mar 2021 05:33:35 +0000

Problem Statement

You are given the head of a linked list, and an integer k.

Return the head of the linked list after **swapping **the values of the *kth *node from the beginning and the *kth *node from the end (the list is **1-indexed).

Example 1:

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

Example 2:

**Input:** head = [7,9,6,6,7,8,3,0,9,5], k = 5
**Output:** [7,9,6,6,8,7,3,0,9,5]

Example 3:

**Input:** head = [1], k = 1
**Output:** [1]

Example 4:

**Input:** head = [1,2], k = 1
**Output:** [2,1]

Example 5:

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

Constraints:

The number of nodes in the list is n.
1 <= k <= n <= 105
0 <= Node.val <= 100

Solution

In this problem, we have to swap the k -th node from the beginning with the k -th node from the end. This is a straight forward LinkedList problem.

Here we are using the 4 nodes.

fast— This is the k -th node from the end
slow — This is the k -th node from the start
first & second — They are used for swapping (to increase readability also)

Algorithm:

First travel k-1 nodes with the fast node. Save the fast node in the first variable.
Now travel till the end of the list, and do fast = fast.next and slow=slow.next .
When fast.next==null , we store the slow in the second variable. This second variable is the position k nodes before the end.
Now swap the values of first and second node.

The code is given below.

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check out my other posts on March LeetCoding Challenge 2021.

March LeetCoding Challenge 2021 — Day 7: Design HashMap

Sourav — Sat, 13 Mar 2021 10:24:42 +0000

Today, we will solve the 7th problem of the March LeetCoding Challenge.

Problem Statement

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

Solution

So in this problem, we are asked to design a HashMap without using any library functions. Here we are going to discuss two approaches to this problem.

Approach 1 — Array: With this approach, we will initialize an array of a certain size with -1. We will use the given key as the index of the array and will store the given value in the array with that index. We can use this method because the key is always positive. This is a pretty straight forward code.

Time Complexity:O(1),for get,put,remove methods

Space Complexity:O(1), the array will occupy 1000001 spaces.

**Approach 2 — LinkedList: **The previous solution was accepted because the key values are not negative. But in general, that is not the case. So we will try to improve the solution and find the hashed index value and store it in the array. To understand the core concepts behind HashMap and it’s internal implement, check out this amazing youtube playlist. (Youtube).

So, by checking the videos we can understand that we may get the same hashed index for different keys(called collision). In order to resolve it, we will use LinkedList.

Let’s go through the whole algorithm once.

Create a ListNode class. It is the node for LinkedList. It stores key and value pair.
Create an array named nodes of ListNode type. It basically works like the HashMap .
In the constructor initialize the array.
put method: At first, find the hashed value for the given key . Check whether any other value is stored at that place or not. If not, create a ListNode with (-1,-1) key-value pair and store it in the nodes array. If it is present, then get the reference to the node (prev). If prev.next is null, then create a new ListNode with key-value pair. Else replace the value of the prev.next node.
get method: Repeat the process of finding hashed value and getting reference to the ListNode(prev). If prev.next is null , then return -1 else return prev.next.value .
remove method: Repeat the process of finding hashed value and getting the reference to the ListNode(prev).To remove that key-value pair from the array, do prev.next=prev.next.next .(Deleting a node from the LinkedList)

The detailed code along with comments is given below.

Time Complexity: O(1) on average, O(n) for worst-case

Space Complexity:O(1), the number of entries is fixed.

The code can be found here.

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check the previous problems for the March LeetCoding Challenge 2021.

Stack Patterns

Sourav — Sat, 13 Mar 2021 09:55:02 +0000

While approaching an algorithmic problem, we should give more attention to the similarities between problems. If we can find these similarities, then solving that kind of problems become very easy. Today we are going to discuss the patterns in the stack.

With this pattern, we can solve a lot of problems based on the stack. We can even solve the popular Stock Span and Maximum Area of Histogram problem.

Approach

Let’s go through the Next Greater Element problem. Here we have to find, the next greater element for each number in an array. We will use the stack to store the greater elements. We will traverse the array backwards.

Algorithm:

Push the last element of the array to the stack
For all the other elements repeat the following process

— Check if the stack is empty,if it is then put -1 at that index. ie. That number does not have any element greater than that to its right side.
— If the peek of the stack is greater than the current element then the stack peek is the next greater element.

— If not, keep popping the top of the stack until you find an element greater than the current element

— If now the stack is empty, place -1 at that index(no greater elements)

— Else peek of the stack is the greater element

— push the current element in the stack

The algorithm can be understood here.

Now you have understood how to solve this problem, you can visualize the other related problems on your own.

If we follow this approach and with little changes we can solve Next Smaller Element, Previous Greater Element and Previous Smaller Element problem easily.

All the four problems along with the java code are given below.

Next Greater Element

Next Smaller Element

Previous Greater Element

Previous Smaller Element

Try these problems by yourself.

In our future tutorials, we will try to extend this problem and use this pattern to solve more problems. You can try the following problems by yourself.

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

March LeetCoding Challenge 2021 — Day 12: Check If a String Contains All Binary Codes of Size K

Sourav — Sat, 13 Mar 2021 09:53:15 +0000

Today, we will solve the 12 th problem of the March LeetCoding Challenge.

Problem Statement

Given a binary string s and an integer k.

Return True if every binary code of length k is a substring of s. Otherwise, return False.

Example 1:

**Input:** s = "00110110", k = 2
**Output:** true
**Explanation:** The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indicies 0, 1, 3 and 2 respectively.

Example 2:

**Input:** s = "00110", k = 2
**Output:** true

Example 3:

**Input:** s = "0110", k = 1
**Output:** true
**Explanation:** The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring.

Example 4:

**Input:** s = "0110", k = 2
**Output:** false
**Explanation:** The binary code "00" is of length 2 and doesn't exist in the array.

Example 5:

**Input:** s = "0000000001011100", k = 4
**Output:** false

Solution

In this problem, we are asked to find whether we have all the binary codes of size k in a given string.

We know that for a given size k, we can have a total of 2^k numbers. We need to check whether all of those 2^k numbers are present in the given string. For that, we can use a HashSet , to store all the values which we have found out. In the end, we can compare the size of HashSet and 2^k , if they are equal then return true else return false.

The code is given below.

Time Complexity: O(n)

Space Complexity: O(n)

The code can be found here

sksaikia / LeetCode

LeetCode

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name	Problem No	Article Links
Contains Duplicate	217	https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0
Jewels and Stones	771	https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37

March LeetCoding Challenge

Problem Name	Problem No	Article Links
Distribute Candies	575	https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9
Set Mismatch	645	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9
Missing Number	268	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb
Intersection of Two Linked Lists	160	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563
Average of Levels in Binary Tree	637	https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8
Short Encoding of Words	820	https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557
Remove Palindromic Subsequences	1332

…

View on GitHub

Check out my other posts on March LeetCoding Challenge 2021.