Dmitrii Volyx

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. ...

134. Gas Station There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique ...

287. Find the Duplicate Number Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and uses only constant extra space. Example 1: Input: nums = [1,3,4,2,2] Output: 2 Example 2: Input: nums = [3,1,3,4,2] Output: 3 Example 3: Input: nums = [1,1] Output: 1 Example 4: Input: nums = [1,1,2] Output: 1 Constraints: ...

621. Task Scheduler Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks. ...

252. Meeting Rooms Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: false Example 2: Input: intervals = [[7,10],[2,4]] Output: true Constraints: 0 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti < endi <= 10^6 Solution class Solution { public boolean canAttendMeetings(int[][] intervals) { if (intervals.length < 2) { return true; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 1; i < intervals.length; i++) { int[] curr = intervals[i]; int[] prev = intervals[i - 1]; if (overlap(prev, curr)) { return false; } } return true; } /* ---------------| |-------------------------- -----------| |-------------- */ boolean overlap(int[] a, int[] b) { return Math.max(a[0], b[0]) < Math.min(a[1], b[1]); } }