Medium

31. Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order). The replacement must be in place and use only constant extra memory. Example 1: Input: nums = [1,2,3] Output: [1,3,2] Example 2: Input: nums = [3,2,1] Output: [1,2,3] Example 3: Input: nums = [1,1,5] Output: [1,5,1] Example 4: Input: nums = [1] Output: [1] Constraints: ...

137. Single Number II Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it. You must implement a solution with a linear runtime complexity and use only constant extra space. Example 1: Input: nums = [2,2,3,2] Output: 3 Example 2: Input: nums = [0,1,0,1,0,1,99] Output: 99 Constraints: 1 <= nums.length <= 3 * 104 -231 <= nums[i] <= 231 - 1 Each element in nums appears exactly three times except for one element which appears once. Solution class Solution { public int singleNumber(int[] nums) { long sum = 0; Set<Integer> set = new HashSet<>(); for (int num: nums) { set.add(num); sum+=num; } long uniqueSum = 0; for (int num: set) { uniqueSum += num; } long remainder = (3 * uniqueSum) - sum; return (int) (remainder / 2); } }

260. Single Number III Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space. Example 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer. Example 2: Input: nums = [-1,0] Output: [-1,0] Example 3: Input: nums = [0,1] Output: [1,0] Constraints: ...

244. Shortest Word Distance II Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array. Implement the WordDistance class: WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict. Example 1: Input ["WordDistance", "shortest", "shortest"] [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]] Output [null, 3, 1] Explanation WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]); wordDistance.shortest("coding", "practice"); // return 3 wordDistance.shortest("makes", "coding"); // return 1 Constraints: ...

245. Shortest Word Distance III Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list. Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list. Example 1: Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1 Example 2: Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes" Output: 3 Constraints: ...

835. Image Overlap You are given two images img1 and img2 both of size n x n, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.) We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images. ...

131. Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. A palindrome string is a string that reads the same backward as forward. Example 1: Input: s = "aab" Output: [["a","a","b"],["aa","b"]] Example 2: Input: s = "a" Output: [["a"]] Constraints: 1 <= s.length <= 16 s contains only lowercase English letters. Solution class Solution { public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); List<String> current = new ArrayList<>(); back(0, s.toCharArray(), current, res); return res; } void back(int index, char[] s, List<String> current, List<List<String>> res) { if (index == s.length) { res.add(new ArrayList<>(current)); return; } for (int i = index + 1; i <= s.length; i++) { if (isPalindrom(s, index, i)) { current.add(new String(Arrays.copyOfRange(s, index, i))); back(i, s, current, res); current.remove(current.size() - 1); } } } boolean isPalindrom(char[] s, int i, int j) { if (i == j) return false; if (j - i == 1) return true; while (i < j) { if (s[i++] != s[--j]) { return false; } } return true; } }

833. Find And Replace in String To some string s, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size). Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing. ...

77. Combinations Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Example 1: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Example 2: Input: n = 1, k = 1 Output: [[1]] Constraints: 1 <= n <= 20 1 <= k <= n Solution class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); List<Integer> current = new ArrayList<>(); back(1, n, k, current, res); return res; } void back(int value, int n, int k, List<Integer> current, List<List<Integer>> res) { if (current.size() == k) { res.add(new ArrayList<>(current)); return; } for (int i = value; i <= n; i++) { current.add(i); back(i + 1, n, k, current, res); current.remove(current.size() - 1); } } }

1041. Robot Bounded In Circle On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions: “G”: go straight 1 unit; “L”: turn 90 degrees to the left; “R”: turn 90 degrees to the right. The robot performs the instructions given in order, and repeats them forever. Return true if and only if there exists a circle in the plane such that the robot never leaves the circle. ...