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

LeetCode - Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Java Solution ;

class Solution {
    public int numIslands(char[][] grid) {
        int numOfIslands = 0;
        for(int i =0; i < grid.length;i++){
            for(int j=0; j < grid[i].length;j++){
                if(grid[i][j] == '1')
                numOfIslands += dfs(grid,i,j);
            }
        }
        return numOfIslands;
    }
    public int dfs (char[][] grid , int i , int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == '0'){
            return 0;
        }
        
        grid[i][j] = '0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
        return 1;
    }
}

LeetCode - Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        int carry = 0;
        ListNode headA =l1 , headB = l2 , curr = temp;
     
           while (headA != null || headB !=null){
                int x = (headA != null) ? headA.val : 0;
                int y = (headB != null) ? headB.val : 0;
                int sum = x + y + carry;
                carry = sum / 10;
                curr.next = new ListNode(sum % 10);     
                curr = curr.next;
               if(headA != null) headA = headA.next;
               if(headB != null) headB = headB.next;
           }
            if(carry > 0)
                curr.next = new ListNode(carry);
            return temp.next;
        
    }
}

Time Complexity : O(max(m,n))

Space Complexity : O(max(m,n))+1

LeetCode - Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Java Solution :

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if(c == '{' || c == '['|| c == '('){
                stack.push(c);
            }else if(c == '}' && !stack.isEmpty() && stack.peek()=='{'){
                stack.pop();
            }else if(c == ']' && !stack.isEmpty() && stack.peek()=='['){
                stack.pop();
            }else if(c == ')' && !stack.isEmpty() && stack.peek()=='('){
                stack.pop();
            }else{
                return false;
            }
        }
        return stack.isEmpty();
    }
}