LeetCode - Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

Java Solution :

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> resultList = new ArrayList<String>();
        for(int i = 1 ; i <= n ; i++){
            if(i%3 == 0 && i%5 == 0)
                resultList.add("FizzBuzz");
            else if(i%3 == 0)
                resultList.add("Fizz");
            else if(i%5==0)
                resultList.add("Buzz");
            else
                resultList.add(Integer.toString(i));
        }
            return resultList;
        }
    
}

LeetCode - Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Java Solution :

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i : nums){
            if(set.contains(i))
                return true;
            else
                set.add(i);
        }
        return false;
    }
}

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;
    }
}