DEV Community: Prashant Mishra

Design LinkedList

Prashant Mishra — Sat, 26 Jul 2025 17:10:30 +0000

class MyLinkedList {
    Node head;
    Node tail;
    int size = 0;
    public MyLinkedList() {
    }

    public int get(int index) {
        if(index<0 || index>=size) return -1;
        Node temp = head;
        int c = 0;
        while(temp!=null){
            if(c == index) return temp.val;
            c++;
            temp = temp.right;
        }
        return -1;
    }

    public void addAtHead(int val) {
        if(head==null && tail==null){
            Node node = new Node(val);
            head = node;
            tail = node;
        }
        else {
            Node node = new Node(val);
            node.right = head;
            head.left  = node;
            head = node;
        }
        size++;
        //print("add at head val: "+ val, head);
    }

    public void addAtTail(int val) {
        if(head==null && tail==null){
            Node node= new Node(val);
            head = node;
            tail = node;
        }
        else{
            Node node = new Node(val);
            tail.right = node;
            node.left = tail;
            tail = node;
        }
        size++;
        //print("add at tail: "+val, head);
    }

    public void addAtIndex(int index, int val) {
        if(index<0 || index> size) return;
        if(index == size){
            //add at tail
            addAtTail(val);
            return;
        }
        else if(index ==0){
            addAtHead(val);
            return;
        }
        //Otherwise add at somewhere in the middle
        Node node = new Node(val);
        Node temp = head;
        int c = 0;
        while(temp!=null){
            if(c == index) break;
            c++;
            temp = temp.right;
        }
        Node leftPartNode  = temp.left;
        node.right = temp;
        temp.left  =node;
        leftPartNode.right = node;
        node.left = leftPartNode;
        size++;
        //print("after add at index "+index +",val "+ val , head);
    }

    public void deleteAtIndex(int index) {
        if(index<0 || index>=size) return;
        if(head == tail){
            head =null;
            tail =null;
            size--;
            return;
        }
        if(index ==0){
            head = head.right;

        }
        else if(index == size-1){
            tail = tail.left;
            tail.right = null;
        }
        else{
            int c= 0;
            Node temp  = head;
            while(temp!=null){
                if(c == index) break;
                c++;
                temp = temp.right;
            }
            Node leftPartNode = temp.left;
            Node rightPartNode = temp.right;
            leftPartNode.right = rightPartNode;
            rightPartNode.left = leftPartNode;
            temp.left  =null;
            temp.right = null;
        }
        size--;
       // print("deletion at index "+index, head);
    }
    public void print(String purpose, Node head){
        System.out.println(purpose + ",current list size "+ size);
        Node temp  = head;
        System.out.print("null<-");
        while(temp!=null){
            System.out.print(temp.val +"->");
            temp = temp.right;
        }
        System.out.print("null");
        System.out.println();
    }
}
class Node{
    Node left;
    Node right;
    int val;
    public Node(int d){
        this.val = d;
    }
    public Node(int d, Node l, Node right){
        this.val = d;
        this.left = l;
        this.right = right;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

Safest Walk through the grid

Prashant Mishra — Sat, 12 Jul 2025 13:51:05 +0000

Problem

class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        Queue<Data> q  = new PriorityQueue<>((a,b)-> Integer.compare(b.h,a.h));
        q.add(new Data(0,0,health-grid.get(0).get(0)));
        int m = grid.size();
        int n = grid.get(0).size();
        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
        int visited[][] = new int[m][n];
        while(!q.isEmpty()){
            Data d = q.remove();
            if(d.i ==m-1 && d.j == n-1) return true;
            for(int dir[] : dirs){
                int i = d.i + dir[0];
                int j = d.j + dir[1];
                if(i>=0 && j>=0 && i< m && j<n && visited[i][j] ==0 && d.h - grid.get(i).get(j) >0){
                    visited[i][j]  = 1;
                    int h = d.h - grid.get(i).get(j);
                    q.add(new Data(i,j,h));
                }
            }
        return false;
    }
class Data{
    int i;
    int j;
    int h;
    public Data(int i, int j, int h){
        this.i = i;
        this.j = j;
        this.h = h;
    }
}

Swim in rising water

Prashant Mishra — Sat, 12 Jul 2025 13:32:50 +0000

Problem

class Solution {
    public int swimInWater(int[][] grid) {
        Queue<Data> q = new PriorityQueue<>((a,b)-> Integer.compare(a.t, b.t));
        q.add(new Data(0,0,grid[0][0]));
        int dirs[][] = {{0,1},{1,0},{0,-1},{-1,0}};
        int visited[][] = new int[grid.length][grid[0].length];
        while(!q.isEmpty()){
            Data d = q.remove();
            if(d.i == grid.length-1 && d.j == grid[0].length-1) {
                return d.t;
            }
            for(int dir[] : dirs){
                int i = dir[0] + d.i;
                int j = dir[1] + d.j;
                if(i>=0 && i< grid.length && j>=0 && j<grid[0].length && visited[i][j]==0 ){
                    visited[i][j] = 1;
                    q.add(new Data(i,j, Math.max(d.t, grid[i][j])));
                }
            }
        }
        return -1;
    }
}
class Data{
    int i;
    int j;
    int t;
    public Data(int i, int j, int t){
        this.i  =i;
        this.j = j;
        this.t = t;
    }
}

Path with minimum effort

Prashant Mishra — Sat, 12 Jul 2025 13:30:07 +0000

Problem

class Solution {
    public int minimumEffortPath(int[][] heights) {
        Queue<Data> q = new PriorityQueue<>((a,b)-> Integer.compare(a.d, b.d));
        q.add(new Data(0,0,0));
        int n = heights.length;
        int m = heights[0].length;
        int min  =Integer.MAX_VALUE;
        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
        int visited[][] = new int[n][m];
        for(int v[] : visited){
            Arrays.fill(v, (int)1e9);
        }
        visited[0][0] = 0;
        while(!q.isEmpty()){
            Data d = q.remove();
            for(int dir[]: dirs){
                int i = d.i + dir[0];
                int j = d.j + dir[1];
                if(i>=0 && j>=0 && i<n && j<m){
                    int maxEffort = Math.max(d.d, Math.abs(heights[i][j] - heights[d.i][d.j]));
                    if(visited[i][j] > maxEffort){
                        visited[i][j] = maxEffort;
                        q.add(new Data(i,j,maxEffort));
                    }
                }
            }  
        }
        return visited[n-1][m-1] == (int)1e9 ? 0: visited[n-1][m-1];
    }
}
class Data{
    int i;
    int j;
    int d;
    public Data(int i ,int j,int d){
        this.i = i;
        this.j = j;
        this.d =d;
    }
}

Decode String

Prashant Mishra — Wed, 02 Jul 2025 17:35:16 +0000

Problem

class Solution {
    public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();
        int i = s.length()-1;
        StringBuilder n= new StringBuilder();
        Stack<Character> stack = new Stack<>();
        while(i>=0){
            while(i>=0 && Character.isDigit(s.charAt(i))){
                n.insert(0,s.charAt(i));
                i--;
            }
            if(n.length()!=0){
                doOp(Integer.parseInt(n.toString()), stack);
                n.setLength(0);
            }
            if(i>=0 && !Character.isDigit(s.charAt(i))){
                stack.push(s.charAt(i));
            }
            i--;
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }
    public static void doOp(int c, Stack<Character> stack){
        stack.pop(); //pop the [ 
        StringBuilder sb = new StringBuilder();
        while(stack.peek()!=']'){
            sb.append(stack.pop());
        }
        if(!stack.isEmpty()){
            stack.pop();//pop the ] 
        }
        char ch[] = sb.toString().repeat(c).toCharArray();
        for(int i =ch.length-1;i>=0;i--){
            stack.push(ch[i]);
        }
    }

}

Bitonic Point

Prashant Mishra — Tue, 01 Jul 2025 16:55:42 +0000

Problem
TC: O(logn)

// User function Template for Java

class Solution {
    public int findMaximum(int[] arr) {
        // code here
        //plain binary search
        int low  =0;
        int high = arr.length-1;
        while(low<high){
            int mid = (low + high)/2;

            if(arr[mid] < arr[mid+1]){
                low = low+1;
            }
            else high = mid;
        }
        return arr[high];
    }
}

Swap Kth node from start and end of a LinkedList

Prashant Mishra — Wed, 25 Jun 2025 12:41:16 +0000

Problem

TC: O(n)
SC: (1)

/**
 * 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 swapNodes(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        while(k-->0){
            prev = fast;
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        int temp = slow.val;
        slow.val = prev.val;
        prev.val = temp;
        return head;
    }
}

Find target in bitonic array with unique elements

Prashant Mishra — Tue, 17 Jun 2025 08:37:02 +0000

TC : O(logn)


class Main {
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,5,4,2};
        int target = 2;
        //find index of 5 in the array
        int peakIndex = findPeak(arr,0,arr.length-1);
        int index = findIndex(arr, target, 0,peakIndex, true);
        if(index!=-1) System.out.println(index);
        System.out.println(findIndex(arr,target, peakIndex+1, arr.length-1, false));

    }
    public static int findIndex(int arr[], int target,int l, int h, boolean increasing){

        while(l<=h){
            int mid = (l+ h) /2;

            if(arr[mid] == target )return mid;

            if(increasing){
                if(arr[mid]<target) l=  mid+1;
                else h = mid-1;
            }
            else{
                if(arr[mid] > target) l = mid+1;
                else h = mid-1;
            }
        }
        return -1;
    }
    public static int findPeak(int arr[], int l, int h){
        while(l<h){
            int mid = (l + h) /2;
            if(arr[mid] < arr[mid+1]) l = mid + 1;
            else h = mid;
        }
        return l;
    }
}

3543. Maximum Weighted K-Edge Path

Prashant Mishra — Wed, 21 May 2025 17:22:26 +0000

Problem

BFS: TLE

class Solution {
    public int maxWeight(int n, int[][] edges, int k, int t) {
        if (k > n)
            return -1;
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++)
            adj.add(new ArrayList<>());
        for (int edge[] : edges) {
            Edge e = new Edge(edge[1], edge[2]);
            adj.get(edge[0]).add(e);
        }
        int maxSum = -1;

        for (int i = 0; i < n; i++) {
            maxSum = Math.max(maxSum, bfs(i, adj, t, k));
        }

        return maxSum;
    }

    public int bfs(int node, List<List<Edge>> adj, int T, int k) {

        Queue<Tuple> q = new LinkedList<>();
        q.add(new Tuple(node, 0, 0));// current node, cost to reach current node, and no of edges so far
        int max = -1;
        while (!q.isEmpty()) {
            Tuple t = q.remove();
            if (t.d < T && t.e == k) {
                max = Math.max(max, t.d);
            }
            for (Edge e : adj.get(t.n)) {
                int sum = t.d + e.c;
                int noOfEdgesSoFar = t.e + 1;
                if (sum < T && noOfEdgesSoFar <= k) {
                    if (noOfEdgesSoFar == k) {
                        max = Math.max(max, sum);
                    } else {
                        q.add(new Tuple(e.n, sum, noOfEdgesSoFar));
                    }
                }

            }
        }
        return max;
    }

}

class Edge {
    int n;
    int c;

    public Edge(int n, int c) {
        this.n = n;
        this.c = c;
    }

}

class Tuple {
    int n;
    int d;
    int e;

    public Tuple(int n, int d, int e) {
        this.n = n;
        this.d = d;
        this.e = e;
    }
}

DFS : TLE

class Solution {
    public int maxWeight(int n, int[][] edges, int k, int t) {
        if(k>n) return -1;
        List<List<Edge>> adj = new ArrayList<>();
        for(int i  =0;i<n;i++) adj.add(new ArrayList<>());
        for(int edge[] : edges){
            Edge e = new Edge(edge[1], edge[2]);
            adj.get(edge[0]).add(e);
        }
        int maxSum = -1;
        for(int i  =0;i<n;i++){
           maxSum  = Math.max(maxSum,dfs(new Tuple(i,0,0),adj,t, k));
        }

        return maxSum;
    }
    public int dfs(Tuple t, List<List<Edge>> adj, int T, int k){
        if(t.e == k){
            if(t.d < T) return t.d;
            return -1;
        }
        int max = -1;
        for(Edge e : adj.get(t.n)){
            int sum = t.d + e.c;
            int noOfEdgesSoFar = t.e + 1;
            if(sum<T && noOfEdgesSoFar<=k){
                max = Math.max(max, dfs(new Tuple(e.n, sum, noOfEdgesSoFar), adj, T, k));
            }
        }
        return max;
    }

}
class Edge{
    int n;//to node
    int c;//edge weight
    public Edge(int n ,int c){
        this.n = n;
        this.c =c;
    }

}
class Tuple{
    int n;//node
    int d;//cost so far
    int e;//noOfEdgesSoFar
    public Tuple(int n ,int d, int e){
        this.n = n;
        this.d = d;
        this.e = e;
    }
}

dp with memoization: works

class Solution {
    public int maxWeight(int n, int[][] edges, int k, int t) {
        if(k>n) return -1;
        List<List<Edge>> adj = new ArrayList<>();
        for(int i  =0;i<n;i++) adj.add(new ArrayList<>());
        for(int edge[] : edges){
            Edge e = new Edge(edge[1], edge[2]);
            adj.get(edge[0]).add(e);
        }
        int maxSum = -1;
        Map<Tuple,Integer> dp = new HashMap<>();
        for(int i  =0;i<n;i++){
           maxSum  = Math.max(maxSum,dfs(new Tuple(i,0,0),adj,t, k,dp));
        }

        return maxSum;
    }
    public int dfs(Tuple t, List<List<Edge>> adj, int T, int k,Map<Tuple,Integer> map){
        if(t.e == k){
            if(t.d < T) return t.d;
            return -1;
        }
        if(map.containsKey(t)) return map.get(t);

        int max = -1;
        for(Edge e : adj.get(t.n)){
            int sum = t.d + e.c;
            int noOfEdgesSoFar = t.e + 1;
            if(sum<T && noOfEdgesSoFar<=k){
                max = Math.max(max, dfs(new Tuple(e.n, sum, noOfEdgesSoFar), adj, T, k,map));
            }
        }
        map.put(t, max);
        return map.get(t);
    } 
}
class Edge{
    int n;
    int c;
    public Edge(int n ,int c){
        this.n = n;
        this.c =c;
    }

}
class Tuple{
    int n;
    int d;
    int e;
    public Tuple(int n ,int d, int e){
        this.n = n;
        this.d = d;
        this.e = e;
    }
    @Override
    public boolean equals(Object o){
        if(o ==null) return false;
        if(o== this) return true;
        if(o.getClass()!= this.getClass()) return false;
        Tuple t = (Tuple) o;
        if(t.n != this.n  || t.d != this.d || t.e != this.e) return false;
        return true;
    }
    @Override
    public int hashCode(){
        return Arrays.hashCode(new int[]{this.n, this.d, this.e});
    }
}

Grid Teleportation Traversal

Prashant Mishra — Sun, 18 May 2025 13:29:58 +0000

Problem

TC : vlogv, where v = m*n

class Solution {
    public int minMoves(String[] matrix) {
        int m = matrix.length;
        int n = matrix[0].length();

        int distance[][] = new int[m][n];
        for(int v[]: distance){
            Arrays.fill(v,Integer.MAX_VALUE);
        }

        Set<String> set = new HashSet<>();// to keep track of distance teleportation cells
        Map<String,List<int[]>> map = new HashMap<>(); // teleportation cells for a given cell [A-Z]
        for(int i =0;i< m;i++){
            for(int j = 0;j<n;j++){
                String str = String.valueOf(matrix[i].charAt(j));
                if(isChar(str)){
                    map.putIfAbsent(str, new ArrayList<>());
                    map.get(str).add(new int[]{i,j});
                }
            }
        }

        int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
        // we have to use dijkstras because the teleportation keeps the moves same
        Queue<Tuple> q = new PriorityQueue<>((a,b)-> Integer.compare(a.c, b.c));
        distance[0][0] = 0;//initial distance
        q.add(new Tuple(0,0,0));
        while(!q.isEmpty()){
            Tuple t  = q.remove();
            if(t.i == m-1 && t.j == n-1) return t.c;
            String str = String.valueOf(matrix[t.i].charAt(t.j));
            if(isChar(str) && !set.contains(str)){
                set.add(str);
                for(int c[] : map.get(str)){
                    if(distance[c[0]][c[1]] > t.c){
                        distance[c[0]][c[1]] = t.c;
                        q.add(new Tuple(c[0],c[1],t.c));
                    }
                }
            }
            for(int dir[] : dirs){
                int i = t.i + dir[0];
                int j = t.j + dir[1];

                if(i<m && j<n && i>=0 && j>=0 && !String.valueOf(matrix[i].charAt(j)).equals("#")){
                    if(distance[i][j] > t.c +1){
                        distance[i][j] = t.c + 1;
                         q.add(new Tuple(i,j, t.c+1));
                    }
                }
            }
        }
        return -1;
    }
    public boolean isChar(String s){
        if(s.equals("#") || s.equals(".")) return false;
        return true;
    }
}
class Tuple{
    int i;
    int j;
    int c;
    public Tuple(int i, int j, int c){
        this.i = i;
        this.j = j;
        this.c = c;
    }
}

Copy Linked List with random pointer

Prashant Mishra — Fri, 18 Apr 2025 15:36:32 +0000

Problem

tc :O(n) where n is no. of nodes in the original linked list
Iterative approach:

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node node = new Node(0);
        Node temp  = node;
        while(head!=null){
            Node duplicateNode = get(map,head);
            temp.next = duplicateNode;
            Node duplicateRandomNode = get(map, head.random);
            duplicateNode.random = duplicateRandomNode;
            temp = temp.next;
            head = head.next;
        }
        return node.next;
    }
    public Node get(Map<Node,Node> map, Node node){
        if(node ==null) return null;
        if(map.containsKey(node)) return map.get(node);
        map.put(node, new Node(node.val));
        return map.get(node);
    }
}

Recursive approach:

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

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        return copy(head,map);

    }
    public Node copy(Node node,Map<Node,Node> map){
        if(node == null) return null;
        if(map.containsKey(node)) return map.get(node);

        map.put(node, new Node(node.val));
        Node duplicate = map.get(node);
        duplicate.next = copy(node.next,map);
        duplicate.random = copy(node.random,map);
        return duplicate;
    }

}

Add 1 to the list

Prashant Mishra — Sun, 06 Apr 2025 12:47:20 +0000

Problem

tc :O(n), sc:O(1)

/*
class Node{
    int data;
    Node next;

    Node(int x){
        data = x;
        next = null;
    }
}
*/

class Solution {
    public Node addOne(Node head) {
        // code here.
        //reverse the list
        //add 1
        ///reverse back again and return
        Node reverseNode = reverse(head);

        head = reverseNode;
        Node prev = null;
        int carry = 1;

        while(head!=null && carry!=0){
            if(head.data + carry > 9){
                int val  = head.data + carry;
                head.data = (val) % 10;
                carry = (val)/10;
            }
            else {
                head.data = head.data+carry;
                carry  =0;
            }
            prev = head;
            head = head.next;
        }

        if(carry!=0){
            prev.next = new Node(carry);
        }
        return reverse(reverseNode);
    }
    public Node reverse(Node node){
        Node prev = null;
        while(node!=null){
            Node next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
}