LeetCode - Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Java Solution :

class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int waterCollected = 0;
        if(height == null || height.length == 0)
            return 0;
        // scan from left to right
        leftMax[0] = height[0];
        int max = leftMax[0];
        for(int i =1 ;i < height.length; i++){
            if(height[i] >= max){
                max = height[i];
                leftMax[i] = max;
            } else{
                leftMax[i] = max;
            }
        }
        
        // scan from right to left
        rightMax[height.length-1] = height[height.length-1];
        int mr = rightMax[height.length-1];
        for(int i = height.length-2; i >= 0 ; i--){
            if(height[i] >= mr){
                mr = height[i];
                rightMax[i] = mr;
            } else{
                rightMax[i] = mr;
            }
        }
        
        for(int i = 0 ;i < height.length; i++){
            waterCollected += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        
        return waterCollected;
    }
}

Design a Tic-tac-toe game Leetcode

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves is allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

Java Solution :

class TicTacToe {
        int[] rowCounter;
        int[] colCounter;
        int diagLeft;
        int diagRight;
        int n;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
         rowCounter = new int[n];
         colCounter = new int[n];
         diagLeft = 0;
         diagRight = 0;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int move = (player == 1) ? 1 : -1;
        rowCounter[row] +=move;
        colCounter[col] +=move;
        if(row == col)
            diagLeft +=move;
        if(row == n-col-1)
            diagRight +=move;
        if(rowCounter[row] == n || diagLeft == n || diagRight== n || colCounter[col] == n)
            return 1;
        else if(rowCounter[row] == -n || diagLeft == -n || diagRight== -n || colCounter[col] == -n)return 2;
        else
            return 0; 
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

LeetCode - Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves is allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

Java Solution :

class TicTacToe {
        int[] rowCounter;
        int[] colCounter;
        int diagLeft;
        int diagRight;
        int n;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
         rowCounter = new int[n];
         colCounter = new int[n];
         diagLeft = 0;
         diagRight = 0;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int move = (player == 1) ? 1 : -1;
        rowCounter[row] +=move;
        colCounter[col] +=move;
        if(row == col)
            diagLeft +=move;
        if(row == n-col-1)
            diagRight +=move;
        if(rowCounter[row] == n || diagLeft == n || diagRight== n || colCounter[col] == n)
            return 1;
        else if(rowCounter[row] == -n || diagLeft == -n || diagRight== -n || colCounter[col] == -n)return 2;
        else
            return 0; 
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

LeetCode - K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

Java Solution :

class Solution {
    public int[][] kClosest(int[][] points, int K) {
 PriorityQueue<int[]> maxHeap = new PriorityQueue<>(Comparator.comparing(a -> -a[0] * a[0] - a[1] * a[1]));        
        for(int[] point : points){
            maxHeap.add(point);
            if(maxHeap.size() > K)
                maxHeap.remove();
        }
        
        int[][] result = new int[K][2];
       
        while(K-- > 0){
            result[K] = maxHeap.poll();
        }
        
        return result;
    }
}

LeetCode - Grouped Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Java Solution :

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groupedAnagrams = new ArrayList<>();
        HashMap<String , List<String>> map = new HashMap<>();
        
        for(String s : strs){
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String sortedString = new String(charArray);
            if(!map.containsKey(sortedString)){
                map.put(sortedString,new ArrayList<String>());
            }
            map.get(sortedString).add(s);
        }
         groupedAnagrams.addAll(map.values());
        return groupedAnagrams;
    }
}

LeetCode - Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

Java Solution :

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals,(a,b)-> a[0] - b[0]);
        int numOfMeetingRooms = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();        
        for(int[] interval : intervals){
            if(minHeap.isEmpty()){
                minHeap.offer(interval[1]);
                numOfMeetingRooms++;
            }else if(minHeap.peek() <= interval[0]){
                minHeap.poll();
                minHeap.offer(interval[1]);
            }else{
                minHeap.offer(interval[1]);
                numOfMeetingRooms++;
            }
        }
       return numOfMeetingRooms;
    }
}

LeetCode - Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(ListNode head : lists){
            while(head !=null){
            minHeap.add(head.val);
            head = head.next;
        }
        }
            ListNode dummy = new ListNode(-1);
            ListNode result = dummy;
            while(!minHeap.isEmpty()){
                result.next = new ListNode(minHeap.remove());
                result = result.next;
            }
            return dummy.next;
    }
}