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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

//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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

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!

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:

1. Find max element index in unsorted prefix part.
2. flip array at that index.
3. flip array at index marking the end of unsorted array.
4. 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! ;)

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!

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!