LeetCode [1539] Kth Missing Positive Number

 1539. Kth Missing Positive Number

Easy

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

 

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

 

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public int findKthPositive(int[] arr, int k) { int n = arr.length; //arr[i-1] - i = missed //find max i s.t. arr[i-1] - i < k //return i+k int l = 0, r = n, mid = 0; while(l<=r){ mid = (l+r)/2; int missed = getMissed(arr, mid); if(missed<k && (mid==r || getMissed(arr, mid+1) >= k)) break; else if(missed<k) l = mid+1; else r = mid-1; } return mid+k; } int getMissed(int[] arr, int len){ if(len==0) return 0; else return arr[len-1] - len; } }

LeetCode [1650] Lowest Common Ancestor of a Binary Tree III

 1650. Lowest Common Ancestor of a Binary Tree III

Medium

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q exist in the tree.

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

/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node parent; }; */ class Solution { public Node lowestCommonAncestor(Node p, Node q) { Node root = p; while(root.parent!=null) root = root.parent; return helper(root, p, q); } Node helper(Node node, Node p, Node q){ if(node==null) return null; if(node.val == p.val || node.val == q.val) return node; Node l = helper(node.left, p, q); Node r = helper(node.right, p, q); if(l!=null && r!=null) return node; if(l!=null) return l; return r; } }

LeetCode[1762] Buildings With an Ocean View

1762. Buildings With an Ocean View

Medium

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

 

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

Example 4:

Input: heights = [2,2,2,2]
Output: [3]
Explanation: Buildings cannot see the ocean if there are buildings of the same height to its right.

 

Constraints:

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 109

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public int[] findBuildings(int[] heights) { List<Integer> list = new ArrayList<>(); int n = heights.length; int tall = 0; for(int i = n-1; i>=0; --i){ if(heights[i]>tall){ list.add(0, i); tall = Math.max(tall, heights[i]); } } int[] ret = new int[list.size()]; for(int i=0; i<list.size(); ++i) ret[i] = list.get(i); return ret; } }