Leetcode

1762. Buildings With an Ocean View 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. ...

84. Largest Rectangle in Histogram Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. ...

1360. Number of Days Between Two Dates Write a program to count the number of days between two dates. The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples. Example 1: Input: date1 = "2019-06-29", date2 = "2019-06-30" Output: 1 Example 2: Input: date1 = "2020-01-15", date2 = "2019-12-31" Output: 15 Constraints: The given dates are valid dates between the years 1971 and 2100. Solution import java.time.*; class Solution { public int daysBetweenDates(String date1, String date2) { return Math.abs(countDays(date1) - countDays(date2)); } int [] MONTHS = new int[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int countDays(String date) { String[] parts = date.split("-"); Integer years = Integer.parseInt(parts[0]); Integer months = Integer.parseInt(parts[1]); Integer days = Integer.parseInt(parts[2]); for (int year = 1971; year < years; year++) { if (isLeapYear(year)) { days += 366; } else { days += 365; } } for (int month = 1; month < months; month++) { if (isLeapYear(years) && month == 2) { days += 29; } else { days += MONTHS[month]; } } return days; } boolean isLeapYear(int year) { return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0); } public int daysBetweenDates2(String date1, String date2) { LocalDateTime time1 = LocalDate.parse(date1).atTime(LocalTime.NOON); LocalDateTime time2 = LocalDate.parse(date2).atTime(LocalTime.NOON); Duration duration = Duration.between(time1, time2); return (int) Math.abs(duration.toDays()); } }

827. Making A Large Island You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in grid after applying this operation. An island is a 4-directionally connected group of 1s. Example 1: Input: grid = [[1,0],[0,1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3. Example 2: Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. Example 3: Input: grid = [[1,1],[1,1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4. Constraints: ...

1168. Optimize Water Distribution in a Village There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes. For each house i, we can either build a well inside it directly with cost wells[i - 1] (note the -1 due to 0-indexing), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes, where each pipes[j] = [house1j, house2j, costj] represents the cost to connect house1j and house2j together using a pipe. Connections are bidirectional. ...

1528. Shuffle String A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively. The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]: lefti is the x coordinate of the left edge of the ith building. righti is the x coordinate of the right edge of the ith building. heighti is the height of the ith building. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. ...

1266. Minimum Time Visiting All Points On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points. You can move according to these rules: In 1 second, you can either: move vertically by one unit, move horizontally by one unit, or move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second). You have to visit the points in the same order as they appear in the array. You are allowed to pass through points that appear later in the order, but these do not count as visits. Example 1: Input: points = [[1,1],[3,4],[-1,0]] Output: 7 Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0] Time from [1,1] to [3,4] = 3 seconds Time from [3,4] to [-1,0] = 4 seconds Total time = 7 seconds Example 2: Input: points = [[3,2],[-2,2]] Output: 5 Constraints: ...

218. The Skyline Problem A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively. The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]: lefti is the x coordinate of the left edge of the ith building. righti is the x coordinate of the right edge of the ith building. heighti is the height of the ith building. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0. ...

270. Closest Binary Search Tree Value Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. Example 1: Input: root = [4,2,5,1,3], target = 3.714286 Output: 4 Example 2: Input: root = [1], target = 4.428571 Output: 1 Constraints: The number of nodes in the tree is in the range [1, 104]. 0 <= Node.val <= 10^9 -10^9 <= target <= 10^9 Solution /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { //////////////// O(logN) //////////////////////// public int closestValue(TreeNode root, double target) { int closest = root.val; while (root != null) { if (Math.abs(root.val - target) < Math.abs(closest - target)) { closest = root.val; } root = root.val > target ? root.left: root.right; } return closest; } //////////////// O(N) //////////////////////// int closest; double closestDelta; public int closestValue2(TreeNode root, double target) { closest = root.val; closestDelta = Math.abs((double) root.val - target); find(root, target); return closest; } void find(TreeNode node, double target) { if (node == null) return; double currentDelta = Math.abs((double) node.val - target); if (currentDelta < closestDelta) { closest = node.val; closestDelta = currentDelta; } find(node.left, target); find(node.right, target); } ///////////// In Order Traversal O(N) public int closestValue1(TreeNode root, double target) { Deque<TreeNode> deq = new ArrayDeque<>(); long prev = Long.MIN_VALUE; while (deq.size() > 0 || root != null) { while (root != null) { deq.offerLast(root); root = root.left; } root = deq.removeLast(); if (prev <= target && target < root.val) { if (Math.abs(target - prev) < Math.abs(target - root.val)) { return (int) prev; } else { return root.val; } } prev = root.val; root = root.right; } return (int) prev; } } Solution 2022-01-30 class Solution { public int closestValue(TreeNode root, double target) { int closest = root.val; while (root != null) { if (Math.abs(target - root.val) < Math.abs(closest - target)) { closest = root.val; } root = (root.val > target) ? root.left: root.right; } return closest; } }

71. Simplify Path Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path. In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names. ...