DEV Community: Prashant Mishra

Check if Binary String has atmost One segment of ones

Prashant Mishra — Sat, 17 Oct 2026 11:16:36 +0000

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum  =0;
        for(int i : nums){
            sum+=i;
        }
        if(sum==goal) return 0;
        long x = goal - sum;
        if(Math.abs(x)<=limit) return 1;
        int val = (int) Math.ceil((double)Math.abs(x)/limit);
        return val;


    }
}

Minimum Elements to Add to Form a Given Sum

Prashant Mishra — Sat, 17 Oct 2026 11:14:21 +0000

Problem

class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum  =0;
        for(int i : nums){
            sum+=i;
        }
        if(sum==goal) return 0;
        long x = goal - sum;
        if(Math.abs(x)<=limit) return 1;
        int val = (int) Math.ceil((double)Math.abs(x)/limit);
        return val;


    }
}

Number of Restricted Paths From First to Last Node

Prashant Mishra — Sat, 17 Oct 2026 11:12:39 +0000

Problem

class Solution {
    public int countRestrictedPaths(int n, int[][] edges) {

        List<List<Pair>> adj = new ArrayList<>();
        for(int i= 0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int edge[] : edges){
            int i = edge[0]-1;
            int j = edge[1]-1;
            int w = edge[2];
            adj.get(i).add(new Pair(j,w));
            adj.get(j).add(new Pair(i,w));
        }
        int distance[] = new int[n];
        Arrays.fill(distance,Integer.MAX_VALUE);
        Queue<Pair> q  = new PriorityQueue<>((a,b)-> Integer.compare(a.c, b.c));
        distance[n-1] = 0;
        // dijsktras with last node as source, this way we will have shortest distance to reach to this node from all the other nodes ( because this will compute shortest distance from last node to all the other node hence vice versa is also true)
        q.add(new Pair(n-1, 0));
        while(!q.isEmpty()){
            Pair p = q.remove();
            int node = p.j;
            int cost = p.c;
            if(cost> distance[node]) continue; //additional optimization (code works without this though)
            for(Pair adjPair : adj.get(node)){
                int adjNode = adjPair.j;
                int w = adjPair.c;
                if(distance[adjNode]> cost + w){
                    distance[adjNode] = cost + w;
                    q.add(new Pair(adjNode, distance[adjNode]));
                }
            }
        }
        int dp[] = new int[n];
        Arrays.fill(dp,-1);
        int restrictedPath = dfs(0,distance,adj, n-1, dp);
        return restrictedPath;
    }
    public int dfs(int i,int[] distance, List<List<Pair>> adj, int lastNode, int dp[]){
        if(i == lastNode) return 1;
        if(dp[i]!=-1) return dp[i];
        int count =0;
        for(Pair adjPair: adj.get(i)){
            int j = adjPair.j;
            if(distance[i]<=distance[j]) continue;
            count+=dfs(j, distance, adj,lastNode, dp);
            count= (count) %((int)1e9 + 7);
        }
        return dp[i] = count;
    }
}
class Pair{
    int j;
    int c;
    public Pair(int j ,int c){
        this.j = j;
        this.c = c;
    }
}

Minimum Amount of time to Brew Potion

Prashant Mishra — Fri, 16 Oct 2026 16:55:50 +0000

Problem

/*
Let start[j] denote the time at which potion j starts at wizard 0.
Because each potion passes through every wizard sequentially, the time potion j reaches wizard i is:
start[j] + mana[j]* summation(k=0 to i-1) of skill[k]

Now consider two consecutive potions, j-1 and j.
For every wizard i, potion j must not reach that wizard before the wizard has finished processing potion j-1.
This gives us a constraint on start[j].Your task is to derive the constraint.

The finishing time of potion j-1 at wizard i is:
start[j-1] + mana[j-1] * summation(k =0 to i) of skill[k]

The arrival time of potion j at wizard i is:
start[j] + mana[j] * summation(k =0 to i-1) of skill[k]

Since the wizard must be available when the next potion arrives, we need:
Arrival time of j >= finish time of j-1 
i.e 
start[j] + mana[j] * summation(k =0 to i-1) of skill[k] >= start[j-1] + mana[j-1] * summation(k =0 to i) of skill[k]
Rearrange this inequality to get a lower bound for start[j].

For every wizard i, the lower bound (atleast start time for potion j) i.e start[j] is:
start[j-1] + mana[j-1]*summation(k = 0 to i) of skill[k] - mana[j]*summation(k=0 to i-1) skill[k]

Two important details:
1. For the previous potion, sum skills from 0 through i, inclusive, because wizard i must finish that potion.
2. For the current potion, sum skills from 0 through i-1, because the potion must arrive at wizard i before it starts processing.
Since this condition must hold for every wizard, we take the maximum lower bound across all wizards:
start[j] = Math.max(lowerboundStart[j] for all the wizards i to m-1)

*/

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int m = skill.length;
        int n = mana.length;
        long prefix[] = new long[m];
        long sum  =0;
        for(int i = 0;i<m;i++){
            sum+=skill[i];
            prefix[i] = sum;
        }


        long prevStartTime = 0;
        long prevFinish = prevStartTime + mana[0]*prefix[m-1];

        for(int j = 1;j<n;j++){
            long maxLowestStartTime = Long.MIN_VALUE;
            for(int i = 0;i<m;i++){
                maxLowestStartTime = Math.max(maxLowestStartTime, prevStartTime + mana[j-1]*prefix[i] - ((i-1) < 0 ? 0 : mana[j]*prefix[i-1]));
            }
            prevFinish = maxLowestStartTime + mana[j]*prefix[m-1];
            prevStartTime = maxLowestStartTime;
        }
        return prevFinish;
    }
}

Bust Balloons

Prashant Mishra — Sat, 10 Oct 2026 16:27:02 +0000

Burst Balloons
Refer this for intuition

Memoization

class Solution {
    public int maxCoins(int[] nums) {
        int arr[]  = new int[nums.length+2];
        int dp[][] = new int[arr.length][arr.length];
        for(int d[] : dp)Arrays.fill(d,-1);
        arr[0] = 1;
        arr[arr.length-1] = 1;
        for(int i =1;i<arr.length-1;i++){
            arr[i] = nums[i-1];
        }
        return find(1,nums.length,arr, dp);
    }
    public int find(int i ,int j , int nums[], int [][] dp){
        ///base case
        if(i>j) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        int cost = Integer.MIN_VALUE;
        for(int index = i;index<=j;index++){
            cost = Math.max(cost, nums[i-1]*nums[index]* nums[j+1] + find(i,index-1,nums,dp) + find(index+1,j, nums,dp));
        }
        return dp[i][j]= cost;
    }
}

Tabulation

class Solution {
    public int maxCoins(int[] nums) {
        int arr[]  = new int[nums.length+2];
        arr[0] = 1;
        arr[arr.length-1] = 1;
        for(int i =1;i<arr.length-1;i++){
            arr[i] = nums[i-1];
        }

        int dp[][] = new int[arr.length][arr.length];

        for(int i = nums.length;i>=1;i--){
            for(int j = 1;j<=nums.length;j++){
                if(i>j) continue;
                int cost = Integer.MIN_VALUE;
                for(int index = i;index<=j;index++){
                cost = Math.max(cost, arr[i-1]*arr[index]* arr[j+1] + dp[i][index-1] + dp[index+1][j]);
                }
                dp[i][j]= cost;
            }
        }

        return dp[1][nums.length];
    }
}

Cherry Pickup

Prashant Mishra — Tue, 06 Oct 2026 14:21:18 +0000

Cherry pickup

class Solution {
    public int cherryPickup(int[][] grid) {
        // was able to understand from the post: https://leetcode.com/problems/cherry-pickup/solutions/329945/very-easy-to-follow-step-by-step-recursi-sjpg/
        //instead of moving from 0,0 and m-1,n-1 at the same time have two people moving from the 0,0 position and at any given point of time if both are at the same cell count onlly once.
        int n = grid.length;
        int dp[][][][] = new int[n][n][n][n];
        for(int dp3[][][] : dp){
            for(int dp2[][]: dp3){
                for(int dp1[] : dp2) Arrays.fill(dp1,-1);
            }
        }
        return Math.max(0,max(0,0,0,0,grid.length,grid,dp));
    }
    public int max(int i, int j, int k, int l, int n, int [][] grid, int[][][][]dp){
        //base case
        if(i>=n || j>=n || k>=n || l>=n || grid[i][j] ==-1 || grid[k][l]==-1) return Integer.MIN_VALUE;
         if(i ==n-1 && j ==n-1){
            return grid[i][j];// if any one reached the end return the value at the location
        }
        if(k ==n-1 && l ==n-1){
            return grid[k][l];// if any one reached the end return the value at the location
        }
        if(dp[i][j][k][l]!=-1) return dp[i][j][k][l];
        int cherries = 0;
        if(i==k && j == l){
            cherries+=grid[i][j];//count only once;
        }
        else{
            cherries+=grid[i][j] + grid[k][l];
        }
        cherries+= Math.max(max(i+1,j,k+1,l,n,grid,dp),
        Math.max(max(i+1,j,k,l+1,n,grid,dp),
        Math.max(max(i,j+1,k+1,l,n,grid,dp), 
        max(i,j+1,k,l+1,n,grid,dp))));

        return dp[i][j][k][l] = cherries;

    }
}

Pattern: Array

Prashant Mishra — Wed, 19 Aug 2026 17:34:19 +0000

Longest Subarray with sum K

class Solution {
    public int longestSubarray(int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);//handle subarray that start from index 0: edge case when the length is 1 of the subarray that sums to k
        //example arr[] = [3], k =3, map=[{0,-1}], at 0 prefixSum = 3 and 3-3 = 0 i.e currentIndex i.e 0 - map.get(0) = -1 = 0-(-1) = 1 i.e the length of the subarray
        int prefixSum = 0;
        int len = 0;
        for(int i = 0;i<arr.length;i++){
            prefixSum+=arr[i];
            if(map.containsKey(prefixSum-k)){
                len = Math.max(len, i-map.get(prefixSum-k));
            }
            if(!map.containsKey(prefixSum)) map.put(prefixSum, i);
        }

        return len;

    }
}

Subarray sum equal to k
note: this is exactly same as the above one with slight twist

class Solution {
    public int subarraySum(int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int prefixSum = 0;
        int len = 0;
        int count = 0;
        map.put(0,1);
        for(int i = 0;i<arr.length;i++){
            prefixSum+=arr[i];
            if(map.containsKey(prefixSum-k)){
                //len = Math.max(len, i-map.get(prefixSum-k));
                count+=map.get(prefixSum-k);
            }
            map.put(prefixSum, map.getOrDefault(prefixSum, 0)+1);
            // if(!map.containsKey(prefixSum)) map.put(prefixSum, i);
        }

        return count;
    }
}

1.

Pattern: BST

Prashant Mishra — Fri, 14 Aug 2026 15:05:55 +0000

Delete a node in bst

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return update(root, null, key);
    }

    public TreeNode update(TreeNode root, TreeNode parent, int key){
        if(root==null) return root;
        if(root.val == key){
            TreeNode left = root.left;
            root  = root.right;
            return add(left,root);
        }
        root.left = update(root.left, root,key);
        root.right = update(root.right, root, key);
        return root;
    }

    public TreeNode add(TreeNode node, TreeNode root){
        if(node==null) return root;
        if(root ==null) return node;
        if(root.val > node.val){
            root.left = add(node, root.left);
        }
        else if(root.val < node.val){
            root.right = add(node, root.right);
        }
        return root;
    }
}

Word search

Prashant Mishra — Mon, 13 Jul 2026 17:26:21 +0000

Word search
We have to search if the given word is present in the metric (4 directionally connected cells) or not

class Solution {
    int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
    public boolean exist(char[][] board, String word) {
        int visited[][] = new int[board.length][board[0].length];
        for(int i =0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j]==word.charAt(0)){
                    if(find(0,word,board,i,j,visited)) return true;
                }
            }
        }
        return false;
    }

    public boolean find(int index, String word, char[][] board, int i, int j, int [][] visited){
        if(index == word.length()-1) return true;

        visited[i][j] = 1;
        for(int dir[] : dirs){
            int I = i + dir[0];
            int J = j + dir[1];
            if(I<board.length && I>=0 && J<board[0].length && J>=0 && visited[I][J]==0 && board[I][J] == word.charAt(index+1)) {
                if(find(index+1, word,board,I,J,visited)) return true;
            }
        }
        visited[i][j] = 0;
        return false;
    }
}

N queen Problem

Prashant Mishra — Mon, 06 Jul 2026 15:48:47 +0000

N queen

class Solution {
    List<List<String>> list = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        //try to put in the first row
        char[][] grid = new char[n][n];
        for(char c[] : grid){
            Arrays.fill(c, '.');
        }

        check(0,grid,n);
        return list;
    }

    public void check(int i,char [] grid[], int n){
        if(i>=n){
            found(grid);
            return;
        }
        for(int j = 0;j<n;j++){
            if(canPlace(i,j,grid)){
                grid[i][j] = 'Q';
                check(i+1,grid,n);
                grid[i][j] = '.';
            }
        }
    }
    public void found(char[][] grid){
        List<String> l = new ArrayList<>();
        for(int i =0;i<grid.length;i++){
            l.add(new String(grid[i]));
        }
        list.add(l);
    }
    public boolean canPlace(int i ,int j, char grid[][]){
        //base case
        if(grid[i][j] == 'Q') return false;
        int I = i;
        int J = j;
        //same column back
        while(I>=0){
            if(grid[I][j]=='Q') return false;
            I--;
        }
        I = i;
        J = j;
        //diagonal left up 
       while(I>=0 && J>=0){
            if(grid[I][J]=='Q') return false;
            I--;
            J--;
        }
        I = i;
        J = j;
        //diagonal right up
        while(I>=0 && J<grid[0].length){
            if(grid[I][J]=='Q') return false;
            I--;
            J++;
        }
        return true;
    }
}

Remove Nth node from the end of the LinkedList

Prashant Mishra — Wed, 24 Jun 2026 16:18:49 +0000

Remove Nth node from the end of the linkedlist

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;
        ListNode sec = head;
        while(n-->0){
            first = first.next;
        }
        if(first ==null) return head.next;
        ListNode temp  = sec;
        while(first!=null){
            first = first.next;
            temp  = sec;
            sec = sec.next;
        }
        temp.next = sec == null ? null : sec.next;
        return head;
    }
}

Minimize max distance to gas station

Prashant Mishra — Mon, 22 Jun 2026 16:59:06 +0000

Minimize max distance to gas station

class Solution {
    public double minMaxDist(int[] stations, int K) {
        // code here
        double min = 0;
        double max = 0;
        for(int i =1;i<stations.length;i++){
            max = Math.max(max,stations[i]-stations[i-1]);
        }
        double result = 0.000000;
        while(max-min > 1e-6){
            double mid = (min+max)/2.0;
            if(isPossible(mid,K, stations)){
                max = mid;
            }
            else min = mid;
        }
        return max;
    }
    public boolean isPossible(double dis, int K , int stations[]){
        int count =0;
        for(int i = 1;i< stations.length;i++){
            double gap = stations[i]-stations[i-1];
            count+=  (int) (gap/dis);
            if(gap % dis==0) count--; // very important because if gap is exactly divisible then adding (quotient) no of stations in between i and i-1 wouuld reduce the min distance lower than dis(check value) 
        }
        return count<=K;
    }
}