DEV Community: Dev Nirwal

Leetcode 2351. First Letter to Appear Twice

Dev Nirwal — Thu, 27 Feb 2025 17:23:25 +0000

Problem Link: 2351: Leetcode

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

Intuition

Approach 1: Using frequency array

Approach

Take a boolean array of 26 elements.

Map each character to index such that a - 0, b - 1,...,z-25.

Iterate through the string and set each index to true.

Before setting any index to be true, check if its true already, if yes return that character.

If we reach at the end of the loop return -1 that means our string only contains unique elements.

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

// Approach 1: Using Frequency array
class Solution {
    public char repeatedCharacter(String s) {
        boolean[] freq = new boolean[26];
        for(char c: s.toCharArray()){
            int index = c - 'a';
            if(freq[index] == true) return truec;
            freq[index] = !freq[index];
        }
        return '-1';
    }
}

Intuition

Approach 2: Using bit masking

Approach

Using a 32-bit number to track 26 alphabet characters.

We are mapping each bit for each character since a number has 32 bit.

If any bit is already set to 1 we return that character

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

class Solution {
    // Approach 2: Bit-wise approach.

    public int setKBit(int num, int k) { // Setting the k-bit to 1 in the number num
        return (1 << k) | num;
    }

    public boolean checkKBit(int num, int k) { // checking if kth bit is already one if yes return true
        return ((1 << k) & num) != 0;
    }

    public char repeatedCharacter(String s) {
        int value = 0;
        for (char c : s.toCharArray()) {
            int k = c - 'a'; // mapping a - 0, b-1, c-2 ... z-25 index
            if (checkKBit(value, k))
                return c; // checking for k bit in the number if set to 1 or not
            value = setKBit(value, k); // setting kth bit to 1 for any character
        }
        return '-1';
    }
}

Maximum Absolute Sum of Any Subarray LC - 1749

Dev Nirwal — Wed, 26 Feb 2025 06:12:30 +0000

Question link on leetcode: Leetcode

Intuition

Maximum subarray sum: Kadane's algorithm

Approach

Take two sums, Max subarray sum and Min subarray sum.
Use Kadane's algorithm to find both.
In the last, compare the max sum and min absolute sum and return the max between them.

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int minSum = Integer.MAX_VALUE;
        int currMax = 0;
        int currMin = 0;
        for(int num: nums){
            currMax +=num;
            currMin +=num;
            maxSum = Math.max(maxSum,currMax);
            minSum = Math.min(minSum,currMin);
            if(currMax<0) currMax = 0;
            if(currMin>0) currMin = 0;
        }
        return Math.max(maxSum,Math.abs(minSum));
    }
}

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

Reorder List: LC 143 medium, GFG hard

Dev Nirwal — Mon, 27 Jan 2025 14:52:30 +0000

Problem Link: Leetcode, Geeks for geeks

Intuition

We need to divide two pointers one at start and one at bottom

Approach

Step 1: first find the mid point of the linked list using slow-fast pointer approach.

Step 2: Divide the linked list into two two by two pointers firstHalf and secondHalf.

Step 3: Use reverse() to reverse the second half of the list.

Step 4: For the final step combined the reversed second half and first half to get the final result.

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        while(next!=null){
            curr.next = prev;
            prev = curr;
            curr = next;
            next = next.next;
        }
        curr.next = prev;
        return curr;
    }
    public void reorderList(ListNode head) {
        if(head == null || head.next == null ) return;
        // use turtle rabbit method, slow-fast pointer to find middle of the linkedlist 
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next; // move once
            fast = fast.next.next; // move twice faster 
        }
        // Divide the linkedList into two parts;
        ListNode secondHalf = slow.next;
        // Set first half next to null to deattach the flist 
        slow.next = null;
        // reverse the second half
        secondHalf = reverse(secondHalf);
        ListNode firstHalf  = head;
        ListNode temp = secondHalf;
        // combinig both list
        while(secondHalf!=null){
            temp = temp.next;
            secondHalf.next = firstHalf.next;
            firstHalf.next  = secondHalf;
            firstHalf = secondHalf.next;
            secondHalf = temp;
        }
        return;
    }
}

GitHub repo for more solutions: Git

Leetcode profile: Leetcode: devn007

Geeks for geeks profile: GFG: devnirwal16

Leetcode 901. Online Stock Span

Dev Nirwal — Sun, 19 Jan 2025 07:22:26 +0000

Intuition

Could you use the answer of previous spans?

Approach

Save the price and its span in the array.

Whenever the last value is less than the current day value, jump to the day of the last day span.

Complexity

Time complexity: O(n)
Space complexity: O(n)

Code

class StockSpanner {
    ArrayList<Pair<Integer,Integer>> list;

    public StockSpanner() {
        list = new ArrayList<>();
    }

    public int next(int price) {
        int index = list.size() - 1;
        int ans = 1;
        while(index!=-1){
            if(list.get(index).getKey()>price) break;
            int span = list.get(index).getValue();
            ans+=span;
            index-=span;
        }
        list.add(new Pair(price,ans));
        return ans;
    }
}


/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Leetcode 75. Sort Colors

Dev Nirwal — Sat, 11 Jan 2025 08:07:57 +0000

Intuition

The basic intuition comes from sorting.

Approach

In the naive approach, we can sort the array using inbuilt sorting function. The time complexity will be O(N*log(N)).

Optimize: Since we are sorting only three numbers, we can use the concept of counting sort. Keep track of number of zeros and number of ones in the array.

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

class Solution {
    public void sortColors(int[] nums) {
        int countZero = 0;
        int countOne  =  0;
        for(int num: nums){
            switch(num){
                case 0:
                    countZero++;
                    break;
                case 1:
                    countOne++;
            }
        }
        int currentIndex = -1;
        while(0<countZero--){
            nums[++currentIndex] = 0;
            // countZero--;
        }
        while(0<countOne--){
            nums[++currentIndex] = 1;
            // countOne--;
        }
        while(currentIndex<nums.length-1){
            nums[++currentIndex] = 2;
        }
    }
}

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Kadane's Algorithm: Leetcode 53 Maximum subarray

Dev Nirwal — Fri, 10 Jan 2025 18:05:39 +0000

Intuition

We can build the intuition based on the two-point approach.

Approach

We will start with two variables maxSum and maxTillNow.

The first variable stores the max sum we have attained overall in the array.
The second variable stores the value of the maximum sum attained till the current index. Since the array has a negative value, this value will fluctuate, but whenever we get maxSum < maxTillNow, we update the maxSum.
The final case we have to handle will be if the maximum sum till any index reaches zero, i.e., maxTillNow < 0, reset the maxTillNow = 0 at the end of loop.

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Leetcode: 73 Set Matrix Zeroes

Dev Nirwal — Fri, 10 Jan 2025 08:24:26 +0000

Intuition

In a naive solution, we can keep track of all the rows and columns to be made zero.

Approach

In the naive solution, we can use hash sets or sets to keep track of rows and columns to make zero using one iteration. In the second phase, we can iterate through our sets to set the saved rows and columns to zero.

Space complexity for Naive Solution: O(M+N)
Naive solution code:

class Solution {
    public void setRowZero(int[][] matrix, int row){
        for(int i = 0;i<matrix[0].length;i++){
            matrix[row][i] = 0;
        }
   }
    public void setColZero(int[][] matrix, int col){
        for(int i = 0;i<matrix.length;i++){
            matrix[i][col] = 0;
        }
    }
    public void setZeroes(int[][] matrix) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        for(int i =0;i<matrix.length;i++){
            for(int j = 0;j<matrix[i].length;j++){
                if(matrix[i][j] == 0){
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        for(int ele: rowSet){
            setRowZero(matrix,ele);
        }
        for(int ele: colSet){
            setColZero(matrix,ele);
        }     
    }
}

In the below solution which is optimized, I have marked the first row and first column if we encounter any zero in the submatrix

[ (1, rows): (1, cols) ]

We can use two boolean variables to keep track of the first row and first column for any zero.

Complexity

Time complexity: O(M * N)
Space complexity: O(1)

Code

class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        boolean first_row_has_zero = false;
        boolean first_col_has_zero = false;

        // check if first row has any zero
        for(int c = 0;c<cols;c++){
            if(matrix[0][c] == 0){
                first_row_has_zero = true;
                break;
            }
        }

        // check if first col has any zero
        for(int r = 0;r<rows;r++){
            if(matrix[r][0] == 0){
                first_col_has_zero = true;
                break;
            }
        }
        // checking for zero elsewhere and keeping track of it in the first row and first column
        for(int r = 1;r<rows;r++){
            for(int c = 1;c<cols;c++){
                if(matrix[r][c] == 0){
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }

        // checking and setting respcted row to zero
        for(int c = 1;c<cols; c++){
            if(matrix[0][c] == 0){
                for(int r = 0;r<rows;r++){
                    matrix[r][c] = 0;
                }
            }
        }

        // checking and setting respcted cols to zero
        for(int r = 1;r<rows; r++){
            if(matrix[r][0] == 0){
                for(int c = 0;c<cols;c++){
                    matrix[r][c] = 0;
                }
            }
        }

        if(first_row_has_zero == true){
            for(int c = 0;c<cols;c++){
                matrix[0][c] = 0;
            }
        }

        if(first_col_has_zero == true){
            for(int r = 0;r<rows;r++){
                matrix[r][0] = 0;
            }
        }

    }
}

GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007

Leetcode Solution - Github automation

Dev Nirwal — Sat, 08 Jan 2022 06:35:45 +0000

Hello everyone, I have found a awesome tool which automatically sync your leetcode solution to your github which I am personally using from many months.

Cons - Only available for chromium based browser.

Extension link - https://chrome.google.com/webstore/detail/leethub/aciombdipochlnkbpcbgdpjffcfdbggi

My leetcode profile - https://leetcode.com/devn007

My github repo to leetcode solutions (java) - https://github.com/devn913/leetcode

My github profile - https://github.com/devn913

SMS Bomber App - Flutter

Dev Nirwal — Sun, 21 Nov 2021 12:26:09 +0000

Note:- This app is only for educational purpose only. Please don't abuse the app or the API. Use it for fun not for revenge.

About this app:- This is one of my small project to prank your friends which send bulk sms in a short period of time. Based on Flutter and Dart and for back-end I have used https://github.com/devn913/bomber_api which is hosted on free Heroku tier.

I am not a Flutter developer so if you have any ideas how to make this app better, I am open to contribution make sure to Fork it star it and follow me if you liked this project.

If you want me to add more API contact me by mail - devnirwal16@gmail.com

If you want to add more API yourself use this repo - https://github.com/devn913/bomber_api

Project GitHub Link - https://github.com/Devn913/bomber_app

APK link - https://github.com/Devn913/bomber_app/blob/main/app-release.apk

My GitHub Profile https://github.com/Devn913

Virus Total - https://www.virustotal.com/gui/file/5f1c9a5eddddd14da717d0681d892665e946517f0b18c5a5ac7e6e2da4d6ffc1?nocache=1

Star it, Follow me if you liked this project.

Contact me if you are facing any issues.

Hacktoberfest - 2021

Dev Nirwal — Mon, 25 Oct 2021 07:03:03 +0000

I am very happy to share this was my first open-source contribution. I'm so happy to announce that. If you haven't submitted yet you should it really feels good. :D

My github Profile - https://github.com/devn913

Quoted Image App

Dev Nirwal — Sun, 03 Oct 2021 20:30:27 +0000

Well one more open-source mini-project by me.

What does it do?
-> In very simple word, it takes a random image from Unsplash API, fetch a quote from quote API and combine them and generate a new Quote Image (like motivational Image)

App link - https://quotedimage.herokuapp.com/

Source Code - https://github.com/devn913/quoted_image_app

Technology Used - Python-Django, Python-pillow, Unsplash-Image API, Quote API, IMGBB API, Tailwind CSS.

Check out source code for more info.

I'm open for suggestions & help.

Star repo if you liked my work.

Keep coding.

Shorti - Opensource URL Shortener

Dev Nirwal — Thu, 23 Sep 2021 09:04:04 +0000

Shorti - A free & Open-source URL shortener.

Here's a screeshot of UI:

This is my first Django project. I got the idea of from many URL shortener which shows ads for money and bitly. I wanted to creare something like that which doesn't have any ads & anyone can understand how things work behind the back.

I have used Python-Django framerwork & tailwind CSS in this small project.

Github link - https://github.com/devn913/shorti

Heroku link - https://shortii.herokuapp.com/

If you want to deploy your own just fork the repository and don't forget to change value of domain = "localhost:8000" in Shorti/url_short/views.py

Make sure to star this if you found something interesting.