Array

Given two integer arrays of equal length target and arr. In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps. Return True if you can make arr equal to target, or False otherwise. Example 1: Input: target = [1,2,3,4], arr = [2,4,1,3] Output: true Explanation: You can follow the next steps to convert arr to target: 1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3] 2- Reverse sub-array [4,2], arr becomes [1,2,4,3] 3- Reverse sub-array [4,3], arr becomes [1,2,3,4] There are multiple ways to convert arr to target, this is not the only way to do so. Example 2: Input: target = [7], arr = [7] Output: true Explanation: arr is equal to target without any reverses. Example 3: Input: target = [1,12], arr = [12,1] Output: true Example 4: Input: target = [3,7,9], arr = [3,7,11] Output: false Explanation: arr doesn't have value 9 and it can never be converted to target. Example 5: Input: target = [1,1,1,1,1], arr = [1,1,1,1,1] Output: true Constraints: ...

Given a URL startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl. Return all URLs obtained by your web crawler in any order. Your crawler should: Start from the page: startUrl Call HtmlParser.getUrls(url) to get all URLs from a webpage of a given URL. Do not crawl the same link twice. Explore only the links that are under the same hostname as startUrl. As shown in the example URL above, the hostname is example.org. For simplicity’s sake, you may assume all URLs use HTTP protocol without any port specified. For example, the URLs http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while URLs http://example.org/test and http://example.com/abc are not under the same hostname. ...

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer. Example 1: Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6 Example 2: Input: arr = [1,1] Output: 1 Constraints: 1 <= arr.length <= 10^4 0 <= arr[i] <= 10^5 Solution class Solution { public int findSpecialInteger2(int[] arr) { int n = arr.length; int val1 = arr[n / 4]; int val2 = arr[n / 4 * 2] ; int val3 = arr[n / 4 * 3]; int val4 = arr[n - 1]; int count1 = countFreq(arr, val1); int count2 = countFreq(arr, val2); int count3 = countFreq(arr, val3); int count4 = countFreq(arr, val4); if (count1 >= count2 && count1 >= count3 && count1 >= count4) { return val1; } if (count2 >= count1 && count2 >= count3 && count2 >= count4) { return val2; } if (count3 >= count1 && count3 >= count2 && count3 >= count4) { return val3; } return val4; } int countFreq(int[] arr, int val) { int mid = Arrays.binarySearch(arr, val); int right = mid; while (right < arr.length - 1 && arr[right] == arr[right + 1]) { right++; } int left = mid; while (left > 0 && arr[left] == arr[left - 1]) { left--; } return right - left; } } Solution 2 class Solution { public int findSpecialInteger(int[] arr) { int n = arr.length; int t = n / 4; for (int i = 0; i < n - t; i++) { if (arr[i] == arr[i + t]) { return arr[i]; } } return -1; } }

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums. A subarray is a contiguous subsequence of the array. Example 1: Input: nums = [1,2,3,4] Output: 3 Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself. Example 2: Input: nums = [1] Output: 0 Constraints: ...

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. ...

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right. When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time. ...

Given an array nums and an integer target. Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target. Example 1: Input: nums = [1,1,1,1,1], target = 2 Output: 2 Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2). Example 2: Input: nums = [-1,3,5,1,4,2,-9], target = 6 Output: 2 Explanation: There are 3 subarrays with sum equal to 6. ([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping. Example 3: Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10 Output: 3 Example 4: Input: nums = [0,0,0], target = 0 Output: 3 Constraints: ...

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums. Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1). ...

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9 Constraints: 0 <= nums.length <= 105 -10^9 <= nums[i] <= 10^9 DFS Solution class Solution { public int longestConsecutive(int[] nums) { int n = nums.length; if (n == 0) return 0; Arrays.sort(nums); int max = 1; int currentMax = 1; for (int i = 1; i < n ; i++) { if (nums[i] - nums[i - 1] == 0) { continue; } else if (nums[i] - nums[i - 1] == 1) { currentMax++; max = Math.max(max, currentMax); } else { currentMax = 1; } } return max; } }

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). Example 2: Input: nums = [0,0,0], target = 1 Output: 0 Constraints: ...