Leetcode

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

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. ...

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

Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise. A string is represented by an array if the array elements concatenated in order forms the string. Example 1: Input: word1 = ["ab", "c"], word2 = ["a", "bc"] Output: true Explanation: word1 represents string "ab" + "c" -> "abc" word2 represents string "a" + "bc" -> "abc" The strings are the same, so return true. Example 2: Input: word1 = ["a", "cb"], word2 = ["ab", "c"] Output: false Example 3: Input: word1 = ["abc", "d", "defg"], word2 = ["abcddefg"] Output: true Constraints: ...

259. 3Sum Smaller Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target. Example 1: Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3] Example 2: Input: nums = [], target = 0 Output: 0 Example 3: Input: nums = [0], target = 0 Output: 0 Constraints: ...

Two/Three Sum Workout https://leetcode.com/problems/two-sum/ class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> valueIndex = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer find = valueIndex.get(target - nums[i]); if (find != null) { return new int[] {find, i}; } valueIndex.put(nums[i], i); } return new int[] {-1, -1}; } } https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ class Solution { public int[] twoSum(int[] numbers, int target) { int lo = 0; int hi = numbers.length - 1; while (lo < hi) { if (numbers[lo] + numbers[hi] == target) { return new int[] {lo + 1, hi + 1}; } else if (numbers[lo] + numbers[hi] > target) { hi--; } else { lo++; } } return new int[] {-1, -1}; } } https://leetcode.com/problems/3sum/ ...

315. Count of Smaller Numbers After Self You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Example 1: Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Example 2: Input: nums = [-1] Output: [0] Example 3: Input: nums = [-1,-1] Output: [0,0] Constraints: ...

350. Intersection of Two Arrays II Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order. Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted. Constraints: ...

255. Verify Preorder Sequence in Binary Search Tree Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree. Example 1: Input: preorder = [5,2,1,3,6] Output: true Example 2: Input: preorder = [5,2,6,1,3] Output: false Constraints: 1 <= preorder.length <= 10^4 1 <= preorder[i] <= 10^4 All the elements of preorder are unique. Solution class Solution { public boolean verifyPreorder(int[] preorder) { Stack<Integer> stack = new Stack<>(); int lowerBound = Integer.MIN_VALUE; for (int val: preorder) { while (stack.size() > 0 && val > stack.peek()) { lowerBound = stack.pop(); } if (val < lowerBound) { return false; } stack.push(val); } return true; } }