Easy

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL. For example, Given the tree: 4 / \ 2 7 / \ 1 3 And the value to search: 2 You should return this subtree: 2 / \ 1 3 In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL. ...

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Recursive Solution: class Solution { public int climbStairs(int n) { return climbStairs(0, n); } int climbStairs(int i, int n) { if (i > n) return 0; if (i == n) return 1; return climbStairs(i + 1, n) + climbStairs(i + 2, n); } } Recursive Solution with Memo class Solution { public int climbStairs(int n) { int[] memo = new int[n + 1]; return climbStairs(0, n, memo); } int climbStairs(int i, int n, int[] memo) { if (i > n) return 0; if (i == n) return 1; if (memo[i] > 0) { return memo[i]; } return memo[i] = climbStairs(i + 1, n, memo) + climbStairs(i + 2, n, memo); } }

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). Example 1: Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. Example 2: Input: [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2], its length is 1. Note: Length of the array will not exceed 10,000. ...

Given a binary array, find the maximum number of consecutive 1s in this array. Example 1: Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3. Note: The input array will only contain 0 and 1. The length of input array is a positive integer and will not exceed 10,000 Solution: class Solution { public int findMaxConsecutiveOnes(int[] nums) { int sum = 0; int ans = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 1) { sum++; } else { sum = 0; } ans = Math.max(ans, sum); } return ans; } }

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language. Example 1: Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted. Example 2: Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted. Example 3: Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info). Solution: ...

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A. You may return any answer array that satisfies this condition. Example 1: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Note: 1 <= A.length <= 5000 0 <= A[i] <= 5000 Solution: class Solution { public int[] sortArrayByParity(int[] A) { int n = A.length; int i = 0; int j = 1; while (i < n && j < n) { if (A[i] % 2 == 1) { j = i + 1; while (j < n && A[j] % 2 == 1) { j++; } if (j == n) { break; } int c = A[i]; A[i] = A[j]; A[j] = c; } i++; } return A; } }

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even. Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even. You may return any answer array that satisfies this condition. Example 1: Input: [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted. Note: 2 <= A.length <= 20000 A.length % 2 == 0 0 <= A[i] <= 1000 Solution: ...

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Solution: class Solution { public int maxSubArray(int[] nums) { if (nums.length == 1) { return nums[0]; } int dp = nums[0]; int answer = nums[0]; for (int i = 1; i < nums.length; i++) { dp = Math.max(dp, 0) + nums[i]; answer = Math.max(answer, dp); } return answer; } } Solution 2021-11-20 class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n]; int max = nums[0]; for (int i = 0; i < n; i++) { if (i == 0) { dp[i] = nums[i]; } else { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); max = Math.max(dp[i], max); } } return max; } }

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 Solution: class Solution { public int searchInsert(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return l; } }

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz. Example 1: Input: matrix = [ [1,2,3,4], [5,1,2,3], [9,5,1,2] ] Output: True Explanation: In the above grid, the diagonals are: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]". In each diagonal all elements are the same, so the answer is True. Example 2: ...