Let's Code

Sunday, February 14, 2021

HackerRank: Reverse a doubly linked list

Problem Description: https://www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

Runtime complexity of my below code: O(n) where n is the size of the linked list.

Solution approach: Recursive

My Java Solution:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static class DoublyLinkedListNode {
        public int data;
        public DoublyLinkedListNode next;
        public DoublyLinkedListNode prev;

        public DoublyLinkedListNode(int nodeData) {
            this.data = nodeData;
            this.next = null;
            this.prev = null;
        }
    }

    static class DoublyLinkedList {
        public DoublyLinkedListNode head;
        public DoublyLinkedListNode tail;

        public DoublyLinkedList() {
            this.head = null;
            this.tail = null;
        }

        public void insertNode(int nodeData) {
            DoublyLinkedListNode node = new DoublyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
                node.prev = this.tail;
            }

            this.tail = node;
        }
    }

    public static void printDoublyLinkedList(DoublyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
        while (node != null) {
            bufferedWriter.write(String.valueOf(node.data));

            node = node.next;

            if (node != null) {
                bufferedWriter.write(sep);
            }
        }
    }

    // Complete the reverse function below.

    /*
     * For your reference:
     *
     * DoublyLinkedListNode {
     *     int data;
     *     DoublyLinkedListNode next;
     *     DoublyLinkedListNode prev;
     * }
     *
     */
    static DoublyLinkedListNode reverse(DoublyLinkedListNode head) {
        return reverseRecur(head, head.next);
    }
    
    
    private static DoublyLinkedListNode reverseRecur(DoublyLinkedListNode current, DoublyLinkedListNode nextNode) { // 2, 3    3, 4   4, \0
        if (current == null)
            return current;

        if (nextNode == null && current.prev == null) {
            return current;
        }

        //Node nextNode = current.next; 2
        DoublyLinkedListNode prevNode = current.prev; // \0  1 2 3

        if (nextNode == null) {
            current.prev = null;
            return current;  // 4
        }

        //Assume reversed till current.
        DoublyLinkedListNode nextToNext = nextNode.next; // 4  \0

        // 1 <-> 2 <-> 3 <-> 4  ->   4<->3<->2<->1
        nextNode.next = current;  //4 <-> 3 <-> 2 <-> 1 -> \0
        current.prev = nextNode;
        current.next = prevNode;

        return reverseRecur(nextNode, nextToNext); // 3, 4    4, \0

    }


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            DoublyLinkedList llist = new DoublyLinkedList();

            int llistCount = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < llistCount; i++) {
                int llistItem = scanner.nextInt();
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                llist.insertNode(llistItem);
            }

            DoublyLinkedListNode llist1 = reverse(llist.head);

            printDoublyLinkedList(llist1, " ", bufferedWriter);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Do share your thoughts below!

Until next time, Happy Coding!

Become a Patron!

Saturday, January 23, 2021

LeetCode Medium: Open the Lock

Another BFS solvable problem of LeetCode!

Problem Description: https://leetcode.com/problems/open-the-lock/

Problem Approach: BFS

Time Complexity: O(1) as the custom size of state-nodes in this problem is a constant.

Solution:

//public class OpenTheLock {
//}

import java.util.*;

class State {
    String code;
    int dist;
    State(String code, int dist) {
        this.code = code;
        this.dist = dist;
    }
}

class Solution {
    public int openLock(String[] deadends, String target) {

        Set<String> visited = new HashSet<>();
        Set<String> deadendsSet = new HashSet<>();
        for (String d : deadends) {
            deadendsSet.add(d);
        }

        if ("0000".equals(target))
            return 0;
        if (deadendsSet.contains("0000"))
            return -1;

        Queue<State> q = new LinkedList<>();
        q.add(new State("0000", 0));
        visited.add("0000");
        while (!q.isEmpty()) {
            State out = q.remove();
            List<String> neighbours = getNeighbours(out.code);
            for (String n : neighbours) {
                if (!visited.contains(n) && !deadendsSet.contains(n)) {
                    if (n.equals(target))
                        return out.dist+1;
                    State neighState = new State(n, out.dist+1);
                    visited.add(n);
                    q.add(neighState);
                }
            }
        }
        return -1;
    }

    private List<String> getNeighbours(String baseState) {
        List<String> res = new ArrayList<>();
        char[] codeChar = baseState.toCharArray();
        for (int i=0; i<codeChar.length; i++) {
            String neighState = new String();

            String c = ((codeChar[i]-'0')+1)%10 + "";
            for (int idx=0; idx<codeChar.length; idx++)
                if (idx == i)
                    neighState+=c;
                else
                    neighState+=codeChar[idx];
            res.add(neighState);

            neighState = new String();
            c = ((codeChar[i]-'0')+10-1)%10 + "";
            for (int idx=0; idx<codeChar.length; idx++)
                if (idx == i)
                    neighState+=c;
                else
                    neighState+=codeChar[idx];
            res.add(neighState);
        }
        return res;
    }

}

Have fun, until next time!

Become a Patron!

LeetCode Medium: Snakes and Ladders

Here's a problem based on the classical snakes and ladders children's game

Problem Description: https://leetcode.com/problems/snakes-and-ladders

Solution Approach: BFS

Time Complexity: O(V) where V is the number of cells in the board-game and E = 6V.

Solution:

class Solution {
    public int snakesAndLadders(int[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        int maxSq = rows*cols;
        
        boolean visited[] = new boolean[maxSq];
        int[] pred = new int[maxSq+1]; // Allows to print the path as well. Alternatively, a dist[] incrementing at each time can be used too.
        Queue<Integer> squaresQ = new LinkedList<>();
        squaresQ.add(1);
        visited[1] = true;
        pred[1] = 0;
        
        outer:
        while(!squaresQ.isEmpty()) {
            int sqOut = squaresQ.remove();
            
            for (int i=1; i<=6; i++) {
                int neighbourSq = sqOut + i;
                if (neighbourSq > maxSq)
                    break;
                
                int effRow = getEffRow(neighbourSq, rows, cols);
                int effCol = getEffCol(neighbourSq, rows, cols);
                if (board[effRow][effCol] != -1) {
                    neighbourSq = board[effRow][effCol];
                    effRow = getEffRow(neighbourSq, rows, cols);
                    effCol = getEffCol(neighbourSq, rows, cols);
                }
                if (neighbourSq == maxSq) {
                    pred[neighbourSq] = sqOut;
                    break outer;
                }
                
                if (!visited[neighbourSq]) {
                    visited[neighbourSq] = true;
                    pred[neighbourSq] = sqOut; // Alternatively, can do: dist[neighbourSq] = dist[sqOut]++;
                    squaresQ.add(neighbourSq);
                }
                
            }
        }
        
        int cnt = 0;
        int predSq = maxSq;
        if (pred[predSq] == 0)
            return -1;
        while(predSq != 1) {
            cnt++;
            predSq = pred[predSq];
        }
        
        return cnt;
    }
    
    private int getEffRow(int sq, int rows, int cols) {
       return (rows - 1 - (sq-1)/cols);
    }
    
    private int getEffCol(int sq, int rows, int cols) {
        int effCol = (sq -1) % cols; // 0 based
        
        if (((sq - 1)/cols + 1) % 2 == 0) // even row from bottom:1 based
            effCol = cols - 1 - effCol;
        
        return effCol;
    }
}

Until next time,

Happy Coding!

Become a Patron!

Monday, January 18, 2021

LeetCode Medium: Pancake Sorting

Problem of the day: Pancake Sorting

Problem description: https://leetcode.com/problems/pancake-sorting/

Solution Approach:

At every iteration for n-1 iterations move the max element in unsorted prefix array to the end of it by following the following steps:

Find max element index in unsorted prefix part.
flip array at that index.
flip array at index marking the end of unsorted array.
reduce the pointer marking end of unsorted array by 1 thereby decreasing the unsorted part of the array.

Solution:

  
  class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        if (arr.length<=1) {
            return new ArrayList<>();
        }
        
        List<Integer> maxIndicesSelectedForFlip;
        
        int endOfUnsortedArray = arr.length-1;
        for (int idx=1; idx <= endOfUnsortedArray; idx++) {
            //find maxElement, maxElementIndex
            int maxElement = Integer.MIN_VALUE, maxElementIndex = -1;
            for (int i=0; i < endOfUnsortedArray; i++) {
                if (arr[i]>maxElement) {
                    maxElement = arr[i];
                    maxElementIndex = i;
                }
            }

            //Flip 0->maxElementIndex
            flip(arr, maxElementIndex);
            maxIndicesSelectedForFlip.add(maxElementIndex+1);

            //Flip 0->endOfUnsortedArray
            flip(arr, endOfUnsortedArray);
            maxIndicesSelectedForFlip.add(endOfUnsortedArray+1);
        }
        
        return maxIndicesSelectedForFlip;
        
    }
    
    private void flip(int[] arr, int maxIndex) {
        for (int i=0; i<=maxIndex/2; i++) {
            int tmp = arr[i];
            arr[i] = arr[maxIndex-i];
            arr[maxIndex-i] = tmp;
        }
    }
    
}

Time Complexity: O(n^2)

Space Complexity: In-place sorting: O(1)

Happy Coding! ;)

Saturday, January 9, 2021

LeetCode Medium: Design Circular Queue

Every now and then I come across a LeetCode problem that has test cases which contradict the problem statement. One such problem is #622: Design Circular Queue, a medium level problem on LeetCode.

Problem Description: https://leetcode.com/problems/design-circular-queue/

Time Complexity: O(1) across all methods - enqueue, dequeue, front, rear, isEmpty, isFull.

Design:

class MyCircularQueue {
    int[] arr;
    int front;
    int rear;
    int size;

    public MyCircularQueue(int k) {
        arr = new int[k];
        front = rear = -1;
        size = k;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) {
            // queue is full
            return false;
        }
        if (isEmpty()) {
            front = rear = 0;
            arr[front] = value;
        } else {
            rear = (rear+1)%size;
            arr[rear] = value;
        }
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty())
            return false;
        if (front == rear) {
            front = rear = -1;
        } else {
            rear = (rear-1)%size;
        }
        return true;
    }
    
    public int Front() {
        if (isEmpty())
            return -1;
        return arr[front];
    }
    
    public int Rear() {
        if (isEmpty())
            return -1;
        return arr[rear];
    }
    
    public boolean isEmpty() {
        if (front == rear && front == -1) {
            // queue is empty
            return true;
        }
        return false;
    }
    
    public boolean isFull() {
        if (front == (rear+1)%size)
            return true;
        return false;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

Failing test case:

Input

["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","deQueue","deQueue","isEmpty","isEmpty","Rear","Rear","deQueue"]
[[8],[3],[9],[5],[0],[],[],[],[],[],[],[]]

Output

[null,true,true,true,true,true,true,false,false,9,9,true]

Expected

[null,true,true,true,true,true,true,false,false,0,0,true]

Dear @LeetCode please remove these erroneous test cases from the problem's test suite.

Happy Coding meanwhile!

Sunday, January 3, 2021

LeetCode Medium: Rotate Array

Hello all,

Problem of the day: Rotate Array (rotate towards right, k times)

Link to Problem description: https://leetcode.com/problems/rotate-array/

Solution approach: multiple ways

Solution approach 1:

Brute force moving all elements by 1 position, k times. Time Complexity O(n*k). Not great! In-place, so space complexity O(1).

Solution Approach 2:

Making a temporary copy(tmp) of k rightmost elements. Move all preceding elements towards right maintaining order, by k positions i.e. towards the rightmost end. Copy all tmp elements towards k spaces created at the leftmost end.

  class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n < 2)
            return;
        k = k % n;
    
        int[] tmp = Arrays.copyOfRange(nums, n-k, n); 
        for (int i=n-k; i>=1; i--)
            nums[i+k-1] = nums[i-1];
        for (int i=tmp.length-1; i>=0; i--)
            nums[i] = tmp[i];
        
    }   
  }

Time Complexity: O(n)

Space Complexity: O(k)

Solution 3:

Using in-place reverse array custom method.

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n < 2)
            return;
        k = k % n;
        
        reverse(nums, 0, n-1-k);
        reverse(nums, n-k, n-1);
        reverse(nums, 0, n-1);
    }
    
    public void reverse(int[] arr, int st, int end) {
    	int mid = (end-st+1)%2==0 ? (end+st)/2+1 : (end+st)/2;
        for (int i=st; i<mid; i++) { // < : don't reverse mid with itself on odd nElems
            arr[i] = arr[i] + arr[end-(i-st)];
            arr[end-(i-st)] = arr[i] - arr[end-(i-st)];
            arr[i] = arr[i] - arr[end-(i-st)];
        }
    }
    
}

Time Complexity: O(n)

Space: In-place; O(1).

Happy Coding!

Become a Patron!

Wednesday, December 30, 2020

LeetCode Easy(medium-ish): Subtree of Another Tree

Hello Peeps,

We're getting back in touch with problem solving after a long-long time. I was _really really_ busy with family functions in this break.

Yesterday, I solved this LeetCode problem Subtree of Another Tree categorised as easy on LeetCode. I would say medium would have been a more appropriate categorisation of this recursively solvable problem.

Problem link: https://leetcode.com/problems/subtree-of-another-tree/

Solution Approach: Recursion

Time Complexity: O(n) where n is the number of nodes in the tree s.

Space Complexity: O(h) where h is the height of the tree s.

Solution:

/**
 * 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 boolean isSubtree(TreeNode s, TreeNode t) {
        
        //Main logic
        boolean matchFound = false;
        
        //Base condition
        if (s == null && t == null)
            return true;

        if ((s!=null && t==null) || (s==null && t!=null))
            return false;

        if (s.val == t.val)
            matchFound = matches (s, t);

        if (!matchFound) {
            matchFound = isSubtree(s.left, t);
        }
        if (!matchFound) {
            matchFound = isSubtree(s.right, t);
        }

        return matchFound;
    }
    
    private boolean matches (TreeNode s, TreeNode t) {
        if (s==null && t==null)
            return true;
        if ((s!=null && t==null) || (s==null && t!=null))
            return false;
        if (s.val != t.val)
            return false;
        return matches(s.left, t.left) && matches(s.right, t.right);
    }
}

That's all for now!

Happy Coding!!

Let's Code_

Sunday, February 14, 2021

HackerRank: Reverse a doubly linked list

Saturday, January 23, 2021

LeetCode Medium: Open the Lock

LeetCode Medium: Snakes and Ladders

Monday, January 18, 2021

LeetCode Medium: Pancake Sorting

Saturday, January 9, 2021

LeetCode Medium: Design Circular Queue

Sunday, January 3, 2021

LeetCode Medium: Rotate Array

Wednesday, December 30, 2020

LeetCode Easy(medium-ish): Subtree of Another Tree

Featured Post

interviewBit Medium: Palindrome Partitioning II

Search This Blog