Everything

94 flashcards · Programming Languages · by Steven Bui

1. 125. Valid Palindrome Given a string s, return true if the word in all lowercase and no whitespace/punctuation is a palindrome. ex. Input: s = "A man, a plan, a canal: Panama" Output: true ---------------------------------------------------------------------------------- public boolean method (String s) { .... }

   Approach: Create 2 pointers: left at index 0, and right at the last index. In a while-loop while left is less than right, create 2 inner while-loops that only increment/decrement their respective pointers while left is less than right AND while the character at the current index is not a letter or digit (there is a Character method for this). Then, now that the pointers are on their respective characters, check if the characters are the same lowercase. If not, return false. Otherwise, increment…

2. 1768. Weave Strings Together Given 2 strings word1 and word2, combine the strings one character after the other, starting with word1. If a string is longer than the other, just add the rest of the characters on. ex. Input: word1 = "abc", and word2 = "pqr" Output: "apbqcr" ---------------------------------------------------------------------------------- public String method (String word1, String word2) { .... }

   Approach: First, create a new StringBuilder. Then, get the lengths of word1 and word2, and then find the longest length between the 2 of them. In a for-loop for the length of the longest word, add a character from word1 to the StringBuilder if the index is less than word1's length, and do the same for word2. Code: public String mergeAlternately(String word1, String word2) { ....StringBuilder s = new StringBuilder(); ....int maxLength = Math.max(word1.length(), word2.length()); ....for (int i =…

3. 283. Move Zeroes to End Given an int array nums, move all instances of 0 to the end of the array and all instances of other numbers to the front in their same order. ex. Input: nums = [0, 1, 0, 3, 12] Output: [1, 3, 12, 0, 0] ---------------------------------------------------------------------------------- public void method (int[] nums) { .... }

   Approach: Create 2 pointers at the beginning: slow to keep track of the index that updates the beginning of the array, and fast to traverse the array. While fast traversing the array, check if the value at nums[fast] is not 0. If so, then set nums[slow] to that value, and increment slow. Be sure to increment fast each time too. At the end of the loop, you can use a for-loop to set all of the entries from slow to the end of the array to 0. Code: public void method (int[] nums) { ....int slowInde…

4. 345. Reverse Vowels Given a string s, reverse all of its vowels (a, e, i, o, u). These can be uppercase or lowercase. ex. Input: s = "leetcode" Output: "leotcede" ---------------------------------------------------------------------------------- public String method (String s) { .... }

   Approach: First, create a HashSet containing all of the vowels since contains() is O(1). Then, turn the String to a char array, and set up 2 variables: left to keep track of the starting index of the array, and right to keep tracking of the ending index of the array. While left < right, find the first vowel on the left side by checking if left < right and if the current index is not on a vowel. Do the same for the right side. Then, if left < right still, swap places, increment left, decrement r…

5. 274. H-Index Given an int array citations, return the highest number h such that there are at least h elements in the array that have a value greater than or equal to h. ex. Input: citations = [3, 0, 6, 1, 5] Output: 3 (3 entries (3, 5, 6) have a value greater than or equal to 3) ---------------------------------------------------------------------------------- public int method (int[] citations) { .... }

   Approach: First, sort the array using Arrays.sort(). Then, we can just get the length of the array using array.length. Then, in a for-loop, get the value of h by subtracting length - i. Check if array[i] is greater than or equal to h. If it is, return h. Return 0 at the end. Code: public int method (int[] citations) { ....Arrays.sort(citations); ....int length = citations.length; ....for (int i = 0; i < length; i++) { ........int h = length - i; ........if (citations[i] >= h) { ............retu…

6. 121. Buy and Sell Stock Given an int array prices, return the most profit you can make if you buy stock for prices[i] and sell stock later for prices[i]. You must buy first and then sell. If you cannot get any profit, return 0. ex. Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 (buy for 1, sell for 6) ---------------------------------------------------------------------------------- public int method (int[] prices) { .... }

   Approach: Initialize 2 int variables: minPrice to save the smallest price that we've seen so far, and maxProfit to save the maximum profit we can get so far. For all of the prices in prices, check if that price is less than the minPrice. If so, update minPrice. If not, calculate what profit you would get by subtracting the price from minPrice. If that profit is higher than maxProfit, update maxProfit. Code: public int method (int[] prices) { ....int minPrice = Integer.MAX_VALUE; ....int maxProf…

7. 42. Trapping Rain Water You are given an int array height, which represents the elevations of different bars on a 2D map moving left to right. Return the value of how much water can be trapped after raining. ex. Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 (1 + 4 + 1 = 6) ---------------------------------------------------------------------------------- public int method (int[] height) { .... }

   Approach: Notice how the map creates a "triangle" shape with the peak being near the middle and the height getting lower as you move to the sides. You want to basically start at the sides and keep going until you hit the peak at the middle. Create 2 pointers: left to keep track of the left index, and right to keep track of the right index. Create 2 more variables to keep track of the max height on the left side so far (maxLeft), and the max height on the right side so far (maxRight). Create ano…

8. 80. Remove Duplicates but Keep at Most 2 Given an int array nums in increasing order, remove duplicates in-place (directly operates on the given data structure) so that each unique number shows up at most twice. The numbers should be moved to the start of the array and should only appear at most twice in the same order. The remaining elements can be anything. Return the number of unique elements plus duplicates in nums. ex. Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3] Output: 7 nums = [0, 0, 1, 1,…

   Approach: First, create 2 variables: 1 is a pointer that gives the index when you write to the array, and 1 is a variable that keeps a count of how many times the number has shown up so far (but not necessarily written yet). Set both of these equal to 1 (write, since nums[0] cannot be a duplicate, and count, because count can only either be 1 or 2). Then, create a for-loop for the length of the array starting at i = 1. If the number at nums[i] is equal to the number before it (nums[i - 1]), the…

9. 189. Rotate Array Given an int array nums and an integer k, move all of the entries of nums k spaces to the right. ex. Input: nums = [1, 2, 3, 4, 5, 6, 7], and k = 3 Output: [5, 6, 7, 1, 2, 3, 4] ---------------------------------------------------------------------------------- public void method (int[] nums, int k) { .... }

   Approach: You are going to reverse the entire array first. Then, reverse the first k elements. Finally, reverse the last n-k elements. You will do this by creating you own private method for reversing which takes a start index and ending index. ex. [7, 6, 5, 4, 3, 2, 1] [5, 6, 7, 4, 3, 2, 1] [5, 6, 7, 1, 2, 3, 4] Code: public void method (int[] nums, int k) { ....reverse(nums, 0, nums.length - 1); ....reverse (nums, 0, k - 1); ....reverse (nums, k, nums.length - 1); } private void reverse (int[…

10. 151. Reverse Words in a String Given a string s, reverse the order of the words, separated by a space and no trailing whitespace. ex. Input: s = "the sky is blue" Output: "blue is sky the" ---------------------------------------------------------------------------------- public String method (String s) { .... }

    Approach: First, create a StringBuilder to store the reversed string. Save an index i at 0 and a different one n at the end of the given string s. In a while-loop while i is less than n (while you are not done traversing the given string), skip all whitespace by creating another while-loop while the character at s is whitespace and i < n, where you just increase i. Outside of that inner while-loop, break out of the outer while-loop if i ≥ n. Create another index j that starts at i+1 and keeps g…

11. 383. Ransom Note Say you have 2 strings: ransomNote and magazine. If you can create ransomNote using only the characters in magazine, return true. Assume that both strings only contain lowercase English letters. ex. Input: ransomNote: "aa" magazine" "aab" Output: true ---------------------------------------------------------------------------------- public boolean method (String ransomNote, String magazine) { .... }

    Approach: Create an int array of size 26. Iterate through magazine and increase the count of each character, which has an index at the character - 'a'. For example, the character a in the array has an index at 'a' - 'a' = 0. Then, iterate through ransomNote as a char array. If the value in the array is 0, return false. Otherwise, decrement the value and continue. Code: public boolean method (String ransomNote, String magazine) { ....int[] array = new int[26]; ....for (char c : magazine.toCharAr…

12. 169. Majority Element Given an int array nums of size n, return the majority element (showing up over n/2 times). Assume there is always a majority. ex. Input: nums = [3, 2, 3] Output: 3 ---------------------------------------------------------------------------------- public int method (int[] nums) { .... }

    Approach: Save the first element in the array in a variable called candidate, and keep track of its count as 1. In a for-loop traversing the array, if the next element is the same element, increase the count. If it is not the same element, decrease the count. Once the count is 0, replace the candidate with the current element and reset the count, and keep going. Code: public int method (int[] nums) { ....int candidate = nums[0]; ....int count = 1; ....for (int i = 1; i < nums.length; i++) { ...…

13. 88. Merge Sorted Array Given 2 int arrays in increasing order, array nums1 with m elements and array nums2 with n elements, merge both arrays into nums1, which has a length of m + n. ex. Input: nums1 = [1, 2, 3, 0, 0, 0], and m = 3 nums2 = [2, 5, 6], and n = 3 Output: nums1 = [1, 2, 2, 3, 5, 6] ---------------------------------------------------------------------------------- public void method (int[] nums1, int m, int[] nums2, int n) { .... }

    Approach: Have 3 pointers: 1 points to the largest number element of nums1 (m - 1), 1 points to the largest number element of nums2 (n - 1), and 1 points to the end of the nums1 array (m + n - 1). Until all of the elements from EITHER array have been processed, compare the number at the end of nums1 to the number at the end of num2. If the number at the end of nums1 is larger, put that number at the end of the array and decrement the nums1 pointer, and vice versa. Decrement the end of the array…

14. 26. Remove Duplicates from Sorted Array Given an int array nums in increasing order, remove all duplicate numbers "in-place" (directly operates on the given data structure). The numbers should be moved to the start of the array and should only appear once in the same order. The remaining elements can be anything. Return the number of unique elements in nums. ex. Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] Output: 5 nums = [0, 1, 2, 3, 4, ..., ..., ..., ..., ...] -------------------------------…

    Approach: Have 2 pointers: 'i' increments whenever a new element is found to indicate the index of the next new element to add, and 'j' traverses the array looking for new elements. The number of unique elements to return is equal to i + 1. The for-loop can start at j = 1 because we know that the first element at index 0 cannot be a duplicate. We increase i first, and then we set nums[i] to nums[k]. Code: public int method (int[] nums) { ....int i = 0; ....for (int k = 1; k < nums.length; k++)…

15. 27. Remove Element Given an int array nums and an int val, remove all instances of val from nums "in-place" (directly operates on the given data structure). The elements that are not equal to val should be moved to the start of the array. The remaining elements can be anything. Return the number of instances of val. ex. Input: nums = [3, 2, 2, 3], and val = 3 Output: 2 nums = [2, 2, ..., ...] ---------------------------------------------------------------------------------- public int method (…

    Approach: Create a variable k to keep track of how many instances of val there are. However, k also acts as an index keeping track of where to place non-val elements in the array as we iterate it. In a for-loop, if the element at index i is NOT equal to val, then we place this non-val element at index k and then increment k. We do not increment k if the element IS equal to val, effectively skipping it. Code: public int method ( int[] nums, int val ) { ....int k = 0; ........for (int i = 0; i <…

16. 162. Find Peak Element Given an int array nums, return any index which contains a value that is greater than the 2 values next to it. For indices 0 and n-1, assume that the edge value next to it is smaller, so indices 0 and n-1 could be returned. ex. nums = [1, 2, 3, 1] Output: 2 (since index 2 has a peak) ---------------------------------------------------------------------------------- public int method (int[] nums) { .... }

    Approach: Take a binary search approach. The trick is to realize that if the middle index does not have a peak, then there must be a peak in either the left side or the right side. You will know if you are at a peak when the left index == right index (i.e. the middle index == left == right == a peak index). First, set initialize 2 variables: left at index 0, and right at index n-1. While left is less than right (NOT less than or equal too, since equals means at a peak), get the middle index. If…

17. 74. Find Target in a 2D Matrix Given an m x n integer array matrix where each number is in increasing order from left to right and top to bottom, return true if a target value is in the matrix. ex. Output: true ---------------------------------------------------------------------------------- public boolean method (int[][] matrix, int target) { .... }

    Approach: Take a binary search approach. Treat the 2D matrix as a 1D matrix by setting left to index 0 and right to (rows * cols) - 1. Also set rows and cols variables. While left is less than or equal to right, get the middle index between left and right. You then get the value of this middle index by getting the value at matrix[mid / rows][mid % rows]. Then do regular binary search: If the number is LESS than the target, then change LEFT to be mid + 1. If the target is greater than the target…

18. 35. Find Target With Binary Search Given a sorted integer array nums and an integer target, return the index of the target if it exists, or the index of where the target would be inserted at if it does not exist. ex. nums = [1, 3, 5, 6], and target = 2 Output: 1 ---------------------------------------------------------------------------------- public int method (int[] nums, int target) { .... }

    Approach: Take a binary search approach. First, initialize 2 variables: left is at index 0, and right is at the last index. While left is less than or equal to high, get the middle index between left and right. If the target is at that index, return that index. If the number is LESS than the target, then change LEFT to be mid + 1. If the target is greater than the target, then change right to be mid - 1. Outside of the while-loop, return the left index. Code: public int searchInsert(int[] nums,…

19. 374. Guess the Number You are supposed to guess someone's number, which is between 1 and n. You are already given an API (given below), which returns -1 if you guessed higher than the actual number, 1 if you guessed lower than the actual number, and 0 if you got it. Return the number. ex. Input: n = 10, and actual number = 6 Output: 6 ---------------------------------------------------------------------------------- public int method (int n) { .... } API: int guess (int num)

    Approach: Take a binary search approach. First, initialize 2 variables: low will be set to 1, and high will be set to n (since the number can include 1 and n). While low is less than or equal to high, get the middle number between low and high, and call guess() on that number. If guess() returns -1, then this means you guessed too high, so set the new high limit to mid - 1. If guess() returns 1, then this means you guessed too low, so set the new low limit to mid + 1. Do this until guess() retu…

20. 98. Is the Binary SEARCH Tree Valid Given the root of a binary tree, return true if the tree is a valid binary search tree (meaning left children are less than the node, and right children are greater than the node). ex. Output: false (3 is not between 4 and 5) ---------------------------------------------------------------------------------- public boolean method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. You need to create a helper method that takes the minimum and maximum valid values in a range. First, in the main function, call the helper method using the smallest and largest values possible. Then, create a base case: if the root is null, return true. If the root's value is NOT between the maximum and minimum values, the return false. Then, create a recursive case: call the helper function on the node's left child while changing max to the curr…

21. 103. Level Order Traversal Zig-Zagged Given the root of a binary tree, return the level order traversal of the tree as a list of ArrayLists<Integer>, except the first list order goes left-to-right, the next list order goes right-to-left, and we alternate this pattern. ex. Output: [ [3], [20, 9], [15, 7] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). Before the while-loop, create a boolean value to keep track of whether to order the list left-to-right or not. In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. Right before you go into a for-loop inside of the wh…

22. 102. Level Order Traversal Given the root of a binary tree, return the level order traversal of the tree, except you return a list of ArrayLists<Integer>, where each internal ArrayList holds the contents of each level. ex. Output: [ [3], [9, 20], [15, 7] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. Right before you go into a for-loop inside of the while-loop that runs for the number of nodes in the level, create an ArrayList to add the contents of the level i…

23. 637. Average of Each Level in a Binary Tree Given the root of a binary tree, return the average value of each level in the form of an array. ex. Output: [3, 14.5, 11] ---------------------------------------------------------------------------------- public List<Double> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. In a for-loop inside of the while-loop that runs for the number of nodes in the level, get the node's value, add it to a sum variable, and add the children to the…

24. 199. Binary Tree Right Side Given the root of a binary tree, return the nodes that you can see from top to bottom if you are looking at it from the right side. ex. Output: [1, 3, 4] ---------------------------------------------------------------------------------- public List<Integer> method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. You have to use depth-first search, which basically keeps going down the right side until it hits a null node, after which it goes back up and checks the left side. First, create a base case: if the root is null, return an empty list. After that, call a helper method that keeps track of the current node, the depth level, and the list being returned. Then, create a base case for the helper method: if you are encountering this depth for the first ti…

25. 236. Lowest Common Parent Given the root of a binary tree and 2 other nodes p and q, return the node that is the lowest (aka as far from the root as possible) node that both nodes have as a common parent. A node can be its own parent. ex. Input: p = 5, and q = 1 Output: 3 (3 is the common parent of nodes 5 and 1) ---------------------------------------------------------------------------------- public TreeNode method (TreeNode root, TreeNode p, TreeNode q) { .... }

    Approach: You want to use a recursive approach. The trick is to realize that when we traverse the tree, once we find a node that is either p or q, we want to return that node immediately (to make the variable from the recursive call not null). First, create the base case: if the root is either p, q, or null, return the root (since if it is p or q, then this base case returns a non-null value to the recursive call, and if it is null, then this returns null). Then, create the recursive case: call…

26. 114. Binary Tree to an Unbalanced Tree (in Pre-Order) Given the root of a binary tree, use pre-order traversal (add the node as you touch it on the LEFT side) to edit the tree so that each node's right node is the next node in the pre-order traversal (and the left node is always null). ex. Input: Output: ---------------------------------------------------------------------------------- public void method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. The trick is to look at each left node: if you set the node's left child to be the new right child and then attach the old right child as the child of the new right child, you end up with the unbalanced tree that you want. First, create a base case: if the node is null, just return. Then, create a recursive case: call this method on the node's left child, and then the node's right child (this is pre-order traversal since we start with the left, th…

27. 129. Add Up Root-to-Leaf Numbers Given the root of a binary tree, say each path from root to leaf creates a number (ex. 1 -> 2 -> 3 creates 123). Return the total sum of all paths. ex. Input: root = [1, 2, 3] Output: 25 (12 + 13 = 25) ---------------------------------------------------------------------------------- public int method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. Since you need to keep track of the sum, you need to create a helper method with a TreeNode and integer parameter. First, in the main method, call the helper method on the root and 0 (0 representing the tens place right now, where the root itself is just 1 digit). Then, in the helper method, create a base case: if the root is null, return 0. After that, set the integer to 10 * sum, plus the root's value. Then, if the root is an end node, return th…

28. 112. Does Any Path Add Up to a Sum Given the root of a binary tree and a target integer targetSum, return true if there is any path from the root node to a leaf node (i.e. the last node in a path) that exactly adds up to targetSum. ex. Input: root = [5, 4, 8, 11, ...], and targetSum = 22 Output: true (5 + 4 + 11 + 2 = 22) ---------------------------------------------------------------------------------- public boolean method (TreeNode root, int targetSum) { .... }

    Approach: You want to use a recursive approach. You will call this method over and over, decreasing targetSum on each iteration. First, create a base case: if the root is null, return false. If it is not null, then check is it is the last node in the path (i.e. both children are null). If its value is equal to targetSum, return true. Then, create the recursive case: set the new target value to targetSum minus the current node's value, and call this method on the left and right children with the…

29. 226. Flip Binary Tree Over Y-Axis Given the root of a binary tree, invert the tree (basically flipping it over the y-axis) and return the root. ex. Input: [4, 2, 7, 1, 3, 6, 9] Output: [4, 7, 2, 9, 6, 3, 1] ---------------------------------------------------------------------------------- public TreeNode method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. If you look at the picture, all you have to do is swap the children in each subtree. First, create a base case: if the root is null, return null. Then, create a recursive case: call this method on the left child, and then on the right children, and save the returned nodes in variables. Then, swap the children of the current node since that is what it means to invert the tree. Return the root at the end. Code: public TreeNode method (TreeNode root)…

30. 101. Are the Children Mirrors of Themselves Given the root of a binary tree, return true if the children are mirrors of themselves, meaning that it is symmetric around the root node. ex. Input: [1, 2, 2, 3, 4, 4, 3] Output: true ---------------------------------------------------------------------------------- public boolean method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. However, since you want to check the left and right nodes, calling recursion on this method will NOT work. Instead, create a helper method. First, still in this method, check if the left and right nodes are null. If not, then call the recursive method on the left and right children. First, create a base case: if both left and right are null, then they are both at an end node, so return true. After that, since the base case ensured that the nodes c…

31. 100. Are the Binary Trees Identical Given the roots of two binary trees p and q, return true if they are exactly the same and false otherwise. Having the same nodes but flipped does NOT count as being identical. ex. Input: p = [1, 2, 3], and q = [1, 2, 3] Output: true ---------------------------------------------------------------------------------- public boolean method (TreeNode p, TreeNode q) { .... }

    Approach: You want to use a recursive approach. First, create a base case: if both p and q are null, then they are both at an end node, so return true. Then, create the recursive case: since the base case ensured that the nodes cannot both be null, if either p or q are null, then return false. Likewise, if their values are different, return false. Return this method being called on both p and q's left nodes, AND the method being called on their right nodes. Code: public boolean method (TreeNode…

32. 104. Maximum Depth of a Binary Tree Given the root of a binary tree, return its maximum depth (including the root node). ex. Input: root = [3, 9, 20, null, null, 15, 7] Output: 3 ---------------------------------------------------------------------------------- public int method (TreeNode root) { .... } public class TreeNode { ....int val; ....TreeNode left; ....TreeNode right; }

    Approach: You want to use a recursive approach. First, create a base case: if the current node is null, then return 0. Then, create the recursive case: call the method on the node's left node, and save it in a variable. Then, call the method on the node's right node, and save it in a variable. Since you know that your current node is not null (as checked by the base case), return 1 + the maximum of the left and right variables. Code: public int method (TreeNode root) { ....if (root == null) ...…

33. 219. Contains Duplicate II Given an int array nums, return true if a number appears more than once AND if those two numbers are at most k spaces away from each other. ex. Input: nums = [1, 2, 3, 1], and k = 3 Output: true (Because the number '1' is at indices 0 and 3). ---------------------------------------------------------------------------------- public boolean method (int[] nums, int k) { .... }

    Approach: Create a new HashMap with key=the number itself, and value=the index. If the key already exists in the map, return true if its value is at most k spaces away from the current index. If not, add it. Code: public boolean method (int[] nums, int k) { ....HashMap<Integer, Integer> map = new HashMap<>(); ....for (int i = 0; i < nums.length; i++) { ........if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) ............return true; ........map.put(nums[i], i); ....} ....return false;…

34. 217. Contains Duplicate Given an int array nums, return true if any number appears more than once. ex. Input: nums = [1, 2, 3, 1] Output: true ---------------------------------------------------------------------------------- public boolean method (int[] nums) { .... }

    Approach: Create a new HashSet. However, do NOT use contains(). Instead, realize that add() will return true if the set does not contain the element yet and the element can be added (so it basically returns false if the element exists). Code: public boolean method (int[] nums) { ....HashSet<Integer> set = new HashSet<>(); ....for (int num : nums) { ........if (!set.add(num)) ............return true; ....} ....return false; } Time complexity: O(n) if you go through every entry in nums. Space com…

35. 49. Group the Anagrams Together Given a String array strs, group the anagrams together into an ArrayList, and return an ArrayList of those ArrayLists. ex. Input: strs = ["eat", "ate", "tan", "nat", "bat"] Output" [ ["eat", "ate"], ["tan", "nat"], ["bat"] ] ---------------------------------------------------------------------------------- public List<List<String>> method (String[] strs) { .... }

    Approach: First, create a new HashMap, where the key is the string in sorted alphabetical order, and the value is an ArrayList of Strings that are also anagrams of that key. In a for-each loop for each string in strs, convert the string into a char array, sort it, and turn it back into a string (now in sorted alphabetical order). Check if this sorted word is in the map yet. If not, add it to the map with an empty ArrayList. Then, get the list of anagrams for that string using the map, and add t…

36. 1207. Unique Number of Occurrences Given an int array arr, return true if the each number in the array shows up a unique number of times. In other words, 2 numbers do not show up the same number of times. ex. Input: array = [1, 1, 1, 2, 2, 3] Output: true (1 shows up 3 times, 2 shows up 2 times, etc.) ---------------------------------------------------------------------------------- public boolean method (int[] arr) { .... }

    Approach: First, use a hash map to put each number from the array into the map, where the key is the number itself and the value is how many times it occurs. Then, use a hash set to go through the values() of the map (returning a Collection<>). Use the hash set's add() method to try adding the number to the set, where it returns false if the number cannot be added to the set. Code: public boolean method (int[] arr) { ....HashMap<Integer, Integer> map = new ....HashMap<>(); ....for (int i : arr)…

37. 202. Happy Number Given a number n, return true if for each of the digits in the number (ex. 100 is 1, 0, 0), when you square each digit, you can add them all together to get either 1 or another number that can repeat this process to get to 1. ex. Input: n = 19 Output: true 12 + 02 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 ---------------------------------------------------------------------------------- public boolean method (int n) { .... }

    Approach: First, create a helper method that takes n and returns what the next number would be. In your main method, have a slow pointer that checks the next number 1 at a time, and a fast pointer that checks the next number 2 at a time. Make the slow pointer call the helper method once and the fast pointer call the helper method twice. While fast != 1, move slow forward 1 and fast forward 2. Since the while-loop is while slow != 1, make a check to return false if slow == fast (since this means…

38. 2215. Difference Between 2 Arrays Given 2 int arrays nums1 and nums2, return an ArrayList of size 2, where list.get(0) is an ArrayList containing the elements in nums1 that are not in nums2, and list.get(1) is an ArrayList containing the elements in nums2 that are not in nums1. ex. Input: nums1 = [1, 2, 3], and nums2 = [2, 4, 6] Output: [ [1, 3], [4, 6] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (int[] nums1, int[] nums…

    Approach: Create 2 hash sets. Add all of the contents of the arrays into the corresponding sets. Then, create 2 array lists. Go through the numbers in each set, and if the other set does not contain that number, add it to the list. Make a new array list of array lists, and add those 2 array lists to it. Code: public List<List<Integer>> method (int[] nums1, int[] nums2) { ....Set<Integer> set1 = new HashSet<>(); ....Set<Integer> set2 = new HashSet<>(); ....for (int i : nums1) { ........set1.add(…

39. 205. Isomorphic Strings Given 2 strings s and t, return true if the characters in s can be replaced 1:1 to create t. No 2 characters can map to the same character. You will only be using ASCII characters (256). ex. Input: s = "egg", and t = "add" Output: true ---------------------------------------------------------------------------------- public boolean method (String s, String t) { .... }

    Approach: First, check that s and t are the same length. Then, since you know that you are working with ASCII characters only, create 2 new int arrays of size 256. For each index, check if the value at array1[c1] matches the value at array2[c2]. This value represents the last index that these values were seen, so if the values are different, then return false since there is no 1:1 mapping. Then, set array1[char1] and array2[char2] to i + 1 (NOT i since array values default to 0, and we want to…

40. 242. Valid Anagram Given 2 strings s and t, return true if s and t are anagrams of each other. The strings will only contain lowercase letters. ex. Input: s = "rat", and t = "tar" Output: true ---------------------------------------------------------------------------------- public boolean method (String s, String t) { .... }

    Approach: First, check that the 2 strings are the same length. Then, create a int[] of size 26 since you will only have lowercase letters. In a for-loop for the length of a string, increase the count of the array for s.charAt(i), and decrease the count of the array for t.charAt(i). Then, create a new for-each loop that goes through the array and checks that all values are 0. Code: public boolean method (String s, String t) { ....if (s.length() != t.length()) ........return false; ....int[] arra…

41. 1. Two Sum Given an int array nums and a number target, return the indices of 2 numbers in nums that add up to target. ex. Input: num = [3, 2, 4], and target = 6 Output: [1, 2] ---------------------------------------------------------------------------------- public int[] method (int[] nums, int target) { .... }

    Approach: Create a hash map with the key = number at the index, and value = index. Then, iterate the array and for each number, check if target - number is in the hash map already. If so, return the current index and the hash map's value. Code: public int[] method (int[] nums, int target) { ....HashMap<Integer, Integer> map = new HashMap<>(); ....for (int i = 0; i < nums.length; i++) { ........if (map.containsKey(target - nums[i])) { ............int[] rtn = new int[2]; ............rtn[0] = map.…

42. 290. Word Pattern You have a String pattern, which is a string of random characters, and a String s, which is a string of words separated by spaces. Return true if each character in pattern maps to a word in s in the same order. There must be a 1:1 relationship, so a character cannot map to two words, and vice versa. ex. Input: pattern: "abba" s: "cat dog dog cat" Output: true ---------------------------------------------------------------------------------- public boolean method (String patter…

    Approach: First, use the split() method on the string to get an array of Strings. Return false if the length of this array is different from the length of the pattern. Then, create a single array, where the key is the character of the pattern, and the value is the word. In a for-loop, get the character at index i. If the map already contains this character, return false if map.get(c) is different from the word at index i. If the map does not contain this character, return false if the map alrea…

43. 2095. Skip the Middle Node Given the head of a linked list, skip the node in the middle and return the head of the list. If there is an even number of nodes, remove the node rounding up. ex. Input: head = [1, 2, 3, 4] Output: [1, 2, 4] ---------------------------------------------------------------------------------- public ListNode method (ListNode head) { .... }

    Approach: First, return null if head is null and if head.next is null too (since you'll need to call head.next.next). Then, create 2 pointers: a slow pointer at the head, and a fast pointer at next.next. While fast is not null and fast.next is not null (since you need to call fast.next.next), move the slow pointer ahead 1 and the fast pointer ahead 2. Outside of this while-loop, skip the middle node by setting slow.next. Code: public ListNode method (ListNode head) { ....if (head == null || hea…

44. 61. Rotate Linked List Given the head of a linked list, rotate the list by k spaces. In other words, the first node should be k units to the right, etc. Nodes at the end of the linked list would be at the beginning of the list. ex. Input: head = [1, 2, 3, 4, 5], and k = 2 Output: [4, 5, 1, 2, 3] ---------------------------------------------------------------------------------- public ListNode method (ListNode head, int k) { .... }

    Approach: The strategy is basically making the entire list circular by making the last node's next pointer point to the head node. From there, you see find out what the last node of the returned list would be and then save its next pointer (the new "head") and then set that last node's next pointer point to null, making the list no longer circular. First, traverse the list to get to the last node AND get the length of the list. Set the last node's next to head, making the list circular. Then, f…

45. 328. Odd-Index Even-Index List Given the head of a linked list, rearrange the list so that all of the nodes with odd indices are at the beginning of the list in the same order, and all of the nodes with odd indices are at the end of the list in the same order. The first node is considered ODD, so it should stay at the beginning. ex. Input: head = [2, 1, 3, 5, 6, 4, 7] Output: [2, 3, 6, 7, 1, 5, 4] ---------------------------------------------------------------------------------- public ListNode…

    Approach: First, create 2 pointers: odd is the head of a new linked list that points to head and represents the odd indices, and even is a new linked list that points to head.next and represents the even indices. Also, create another pointer called connect which points to even (you won't use this until the end to connect the 2 linked lists). In a while-loop while even is not null and even.next is not null, make odd's next node point to the next odd-indexed node, and make odd move to that node.…

46. 19. Remove the Nth-to-Last Node Given the head of a linked list, remove the nth node from the end of the linked list and return the head. n starts at 1, so if n is 1, you remove the last node. ex. Input: head = [1, 2, 3, 4, 5], and n = 2 Output: [1, 2, 3, 5] ---------------------------------------------------------------------------------- public ListNode method (ListNode head, int n) { .... }

    Approach: Create 3 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, which is needed to return head. Set dummy.next to head. 1 is called behind and currently points to dummy, and it represents the node that stays n nodes behind the ahead node (also pointing at dummy). You need to use a dummy node instead of just head in case you need to skip the first node. Then, move ahead n spaces ahead of behind while the index of the for-loop is LESS THAN OR EQUAL TO n. Then,…

47. 206. Reverse Linked List Given the head of a linked list, return the reversed linked list. ex. Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1] ---------------------------------------------------------------------------------- public ListNode method (ListNode head) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = null; ....} }

    Approach: First, create 2 pointers: current points to the head and deals with the current node. The pointer prev will point to null right now, but you will add the current node to prev as you traverse the given list. In a while-loop while current is not null, you're going to do 4 steps: Initialize a new node called next, which points to current.next. You need to store next because you're about to change what current.next points to. Set current.next to prev. prev represents the start (index 0) o…

48. 2. Add Two Numbers You are given the heads of 2 different linked lists (l1 and l2), both of which represent a number backwards (ex. 2 -> 4 -> 3 is the number 342). Add the 2 numbers together, and return the head of that linked list. Each node only has 1 digit, and no nodes have leading zeroes. ex. Input: l1 = [2, 4, 3], and l2 = [5, 6, 4] Output: 342 + 465 = 807 ---------------------------------------------------------------------------------- public ListNode method (ListNode l1, ListNode l2) {…

    Approach: First, create 2 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, and 1 is a "current" node for adding onto the dummy node. We never move the dummy node, we will only be moving current. Also, create a variable called "carry" for carrying over a number to add. As long as at least one of the linked lists is not null, set a sum variable to carry first. Then, if l1 is not yet null, add its value to sum and move l1 forward. Do the same for l2. Update carry,…

49. 21. Merge 2 Sorted Lists Given the heads of 2 different linked lists (list1 and list2), combine both of them into one linked list, and return the head of that list. ex. Input: list1 = [1, 2, 4], and list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] ---------------------------------------------------------------------------------- public ListNode method (ListNode list1, ListNode list2) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = nul…

    Approach: First, create 2 pointers: 1 is a "dummy" node which is the node at index -1 of the returned list, and 1 is a "current" node for adding onto the dummy node. We never move the dummy node, we will only be moving current. While both list1 and list2 are not null (aka until one is null), compare the values at list1 and list2 (these are nodes). If list1 value is smaller, then do 3 things: Set current.next to list1 Move list1 forward to list.next Move current forward to current.next Repeat th…

50. 141. Linked List Cycle Given only the start node of the linked list (head), return true if the linked list has a cycle in it. ex. Input: head = [3, 2, 0, -4] Output: true ---------------------------------------------------------------------------------- public boolean method (ListNode head) { .... } class ListNode { ....int val; ....ListNode next; ....ListNode (int x) { ........val = x; ........next = null; ....} }

    Approach: First, check if the head is null (empty list). Then, create 2 pointers: a slow pointer that moves 1 node at a time, and a fast pointer that moves 2 nodes at a tome. While the fast pointer is not null (it is a node) and the fast pointer's next node is not null either, move slow 1 node forward and fast 2 nodes forward. If slow is equal to fast, return false. Code: public boolean method (ListNode head) { ....if (head == null) { ........return false; ....} ....ListNode slow = head; ....Li…

51. 71. Simplify Unix Path You are given the absolute path for a Unix file system (ex. /home/downloads/file), but you need to simplify it: A single period (.) represents the current directory A double period (..) means go back a directory level Multiple periods (....) is the same as a name of a directory level Multiple consecutive slashes (////) are the same as 1 slash The returned path should start with one slash and not end with a slash (unless it is the root '/'). It should also not include (.)…

    Approach: First, create a stack of String objects (each object representing a directory level name). Split the path into a String array. For all of the strings in the array, skip if the string is a period (representing the current directory) or empty (representing a multi-slash). Then, if the string is (..), pop from the stack if it is not empty. Otherwise, add the string to the slash. Then, when you are out of the loop, create a new StringBuilder and append 2 things into the String Builder: a…

52. 20. Valid Parentheses Given a string s which contains parentheses (), curly braces {}, and brackets [], determine if all open characters are closed by closed characters in the same order. ex. Input: ([{}]) Output: true ---------------------------------------------------------------------------------- public boolean method (String s) { .... }

    Approach: Create a stack of characters. For each character in the string, create a switch block, where for each open character, you add onto the stack and break. For every closed character, try popping off the same character but open. If the stack is empty or the character is wrong, return false. At the end, return true if the stack is empty. Code: public boolean method (String s) { ....Stack<Character> stack = new Stack<>(); ....for (char c : s.toCharArray) { ........switch (c) { ............c…

53. 6. Zigzag Conversion Given a string s and the number of rows, create a String that outputs the string's words in a zig zag format like the following (straight down, then top right, then straight down, etc): ex. Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" P ........I ........N A ....L S ....I .G Y..A ...H R P ........I ---------------------------------------------------------------------------------- public String method (String s, int numRows) { .... }

    Approach: First, check if the number of rows is 1, and return the string if so. Otherwise, create a list of StringBuilders, one for each row. Have variables to save the current row (initialized at 0) and the direction (1 if moving down, -1 if moving up). In a for-loop for the length of the string, add the current character to the current row's StringBuilder. If the currentRow is 0 (at the top), then switch the direction to 1. If the current row is at the end, then switch the direction to -1. At…

54. 128. Longest Consecutive Sequence Given an unsorted int array nums, return the length of the longest sequence of consecutive numbers. Note that these numbers do not have to start at 0, nor do they have to be in order. ex. Input: [100, 4, 200, 1, 3, 2] Output: 4 (1, 2, 3, 4) ---------------------------------------------------------------------------------- public int method (int[] nums) { .... }

    Approach: Create a new HashSet, and add all of the numbers from nums into this set. Create a new variable to save the maximum length. In a for-each loop iterating through the set, first check that that 'number - 1' does not exist in the set since you only want to check sequences starting from the smallest number, not the middle of a sequence. From there, save the current number and the current length. In a while-loop while the set contains that 'current number + 1', increase the current number…

55. 160. Where 2 Linked Lists Intersect Given the heads of 2 linked lists headA and headB, return the NODE where the 2 lists intersect, or null if they do no intersect. ex. Input: Output: Node with value 8 ---------------------------------------------------------------------------------- public ListNode method (ListNode headA, ListNode headB) { .... }

    Approach: First, check if either head is null. Then, create 2 new ListNodes that point to the corresponding ListNode heads. The principle behind this solution is that we move each pointer ahead until a pointer gets to the end of its list (null), at which point it will switch over to the other head. Say the first list is length m and the second list is length n. Both lists WILL get to the end of their lists and switch to the other list, and if there is an intersection, then they WILL meet at it…

56. 14. Longest Common Prefix Return the longest common prefix string among an array of strings. ex. Input: ["flower", "flow", "flight"] Output: "fl" ---------------------------------------------------------------------------------- public String method (String[] method) { .... }

    Approach: First, check if the array is null or empty. Then, save the first string of the array. In an outer for-loop from 0 to the length of that first string, save the character at that outer for-loop's index (this outer for-loop goes through the characters of that first string). In an inner for-loop from 1 to the length of the array (skipping 0 since the first string is index 0) (this inner for-loop goes through the strings of the array), check 2 conditions: if the character index is longer t…

57. 1657. Determine if 2 Strings are "Close" 2 strings are considered "close" if you can turn one into the other using these 2 operations (which you can do as many times as you'd like): Swap any 2 characters Transform all of the occurrence of a character into a different character, and do the same for the other character. ex. Input: word1 = "cabbba", word2 = "abbccc" Output: true Operation 1: cabbba -> caabbb Operation 2: caabbb -> baaccc Operation 2: baaccc -> abbccc ------------------------------…

    Approach: The trick is that you don't actually need to keep track of the frequency of each character at all! The principle is that the frequency arrays should be the same (ex. "abbccc" -> [1, 2, 3], "cabbba" -> [1, 2, 3]). First, check if the 2 strings are the same length. Then, create 2 int arrays of size 26 to store the character frequencies of both words. Create 2 for-each loops going through the characters of both words, updating the int arrays based on the character present (using word1.ch…

58. 2352. Equal Row and Columns Given an n*n matrix called grid, return the number of row-column pairs where a sequence in a row (left to right) is the same as a sequence in a column (top to bottom). If there are 2 rows with the same values, include both of them. ex. Input: Output: 3 ([3, 1, 2, 2] from row 1 and col 1) ([2, 4, 2, 2] from row 3 and col 3) ([2, 4, 2, 2] from row 4 and col 3) --------------------------------------------------------------------------------- public int method (int[][] g…

    Approach: First, save n (the length of a row or column). Then, create a HashMap where key=array of a row/column in String form, and value=number of times the array shows up in a ROW (we can't just use a set since duplicates count). First, for all of the ROWS in the matrix, save the array to the map in the form of a String, and save how many it has shown up so far as well. Then, outside of that for-loop, create a new for-loop for all of the COLUMNS in the matrix, keeping in mind that you have to…

59. 1679. Number of Pairs That Add to K Given an int array nums and an int k, return the maximum number of times that you can remove 2 numbers from the array that add to k. ex. Input: nums = [1, 2, 3, 4] and k = 5 Output: 2 (1 and 4, then 2 and 3) --------------------------------------------------------------------------------- public int method (int[] nums, int k) { .... }

    Approach: First, sort the array. Then, save an integer for the count to return. Then, save variables for the start of the array and the end of the array. While the start is less than the end, add nums[start] and nums[end] together. If the sum is equal to k, update both pointers and increase the count. If the sum is less than k, then update the left counter. If the sum is greater than k, update the right counter. Code: public int method (int[] nums, int k) { ....Arrays.sort(nums); ....int count…

60. 122. Best Time to Buy and Sell Stock (Part 2) Given an int array prices, return the most profit you can make if you buy stock for prices[i] and sell stock later for prices[i]. You are able to sell and buy on the same day. If you cannot get any profit, return 0. ex. Input: prices = [7, 1, 5, 3, 6, 4] Output: 4 (1. Buy when price=1, then sell when price=5 (profit=4). 2. Buy when price=3, then sell when price=6 (profit=7).) --------------------------------------------------------------------------…

    Approach: Initialize an int maxProfit to save the most profit. In a for-loop from 1 to the length of the array, check if the current price is greater than the previous price. If it is, then this means that it is a good time to sell (sell high, buy low), so add prices[i] to maxProfit, and subtract prices[i-1] from maxProfit. The principle is that we don't need to worry about the smallest value seen so far. We only care about if the next value we see is higher. Code: public int method (int[] pric…

61. 55. Jump Game Given an int array nums, say that each value nums[i] represents how many spaces ahead you can move forward in the array. You do not have to jump the whole distance (ex. if nums[0] is 3, you can choose to only go 1 space). Return true if you can reach the last index. ex. Input: nums = [2, 3, 1, 1, 4] Output: true --------------------------------------------------------------------------------- public boolean method (int[] nums) { .... }

    Approach: Start from the last index, saving it as the last reachable position. In a for-loop starting at the second to last index and moving while i is greater than or equal to 0, check if that index plus the value at that index is greater than the last reachable position. If so, update the last reachable position to that index. The principle is that this last reachable position represents the earliest index that can reach the end, so we want to return true if after the for-loop, that last reac…

62. 45. Jump Game (Part 2) Given an int array nums, say that each value nums[i] represents how many spaces ahead you can move forward in the array. You do not have to jump the whole distance (ex. if nums[0] is 3, you can choose to only go 1 space). Return the minimum number of jumps to reach the last index, given that every nums array will always reach the end. ex. Input: nums = [2, 3, 1, 1, 4] Output: 2 (1 jump from index 0 to index 1) (1 jump from index 1 to index 4) -----------------------------…

    Approach: First, save the number of jumps to return, the furthest index that we can get to right now if we say that jumps=n (jumpOneLimit), and the furthest index you can get to after this when jumps=n+1 (jumpTwoLimit). In a for-loop for the length of the array, update jumpTwoLimit (representing the farthest distance in the array we can get to based on all the indices seen so far) if it is greater than i + nums[i]. Then, if i = jumpOneLimit (saying that we've traversed this for-loop through all…

63. 41. First Missing Positive Given an unsorted array nums, return the smallest positive number that is not present in the array. You have to do this in O(n) time. ex. Input: nums = [3, 4, -1, 1] Output: 2 --------------------------------------------------------------------------------- public int method (int[] nums) { .... }

    Approach: You will go through the array 3 times. In the first pass, change any entries less than 0 or greater than the length to length+1, which will skip the values in our second pass. In our second pass, get the absolute value of the number at each index. If it is less than n (skipping some entries from our first pass), then mark the number at index-1 as negative (ex. if a number was 3, then nums[2] will be negative). The principle is that the first index that is not negative will give us our…

64. 11. Container With Most Water Given an int array height, where height[i] represents the height of one side of a container, return the maximum amount of water that a container can store. ex. Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 --------------------------------------------------------------------------------- public int method (int[] height) { .... }

    Approach: Use a 2 pointer approach. Save 2 pointers at the start and end of the array. Save 2 variables for the maximum area to return and the height of the shorter side of the container. In a while-loop while left < right, calculate the height of the shorter side and the corresponding maximum area so far. The principle is that we only want to find new heights that are greater than the minimum height, so increase left or decrease right until we find it. Code: public int method (int[] height) {…

65. 15. All Triplets That Add to 0 Given an int array nums, return all triplets that add up to 0, where all of the triplets have different indices and there are no duplicates. ex. Input: nums = [-1, 0, 1, 2, -1, -4] Output: [ [-1, -1, 2], [-1, 0, 1] ] --------------------------------------------------------------------------------- public List<List<Integer>> method (int[] nums) { .... }

    Approach: First, create an ArrayList of ArrayLists to return. Then, sort the array. In a for-loop from 0 to the length of the array - 2 (since this loop only considers the first index of the triplet), skip any duplicates of the first element by checking if nums[i] == nums[i - 1] (to avoid duplicate triplets). Then, use a 2 pointer approach, saving the left side (i+1) and the right side (nums.length-1). In a while-loop while left < right, add up the values at the indices. If the sum is 0, then a…

66. 380. insert(), delete(), and getRandom() Implement a class called RandomizedSet which has a constructor and 3 methods: boolean insert(int val), which returns true if the value is not already in the set boolean remove(int val), which returns true if the item was in the set int getRandom(), which returns a random element from the set. It is guaranteed that there will always be one element when the method is called. All of the functions must have O(1) runtime. ex. Input: RandomizedSet() insert(1)…

    Approach: The constructor will use 2 main data structures: a HashMap where key=number and value=the current size of the map (representing the 'index' in the map) to keep track of element indices, and an ArrayList to keep track of the elements themselves. Also create a Random object here. For the insert method, return false if the map already contains the key. Then, put the number in the map and add the number to the list. For the remove method, return false if the number is not in the map. Then…

67. 238. Product of Array, Except Self Given an int array nums, return another int array where the value at rtn[index] is equal to all of the numbers in nums multiplied by each other except for nums[index]. Do this in O(n) runtime. You cannot use the division operator. ex. Input: nums = [1, 2, 3, 4] Output: [24, 12, 8, 6] --------------------------------------------------------------------------------- public int[] method (int[] nums) { .... }

    Approach: First, save the length of the array, and create an int array to return. The approach is to run through the array twice: the first time to populate the array with the numbers to the left of the index, and the second to multiply the array entries with the numbers to the right of the index. First, save an int for the left initialized at 1, and set rtn[0] to left. Then, in a for-loop starting at 1, set rtn[i] to the multiplication of rtn[i-1] and nums[i-1]. Then, save an int for the right…

68. 200. Number of Islands in a Graph Given an m*n char grid called grid, where 1s represent land and 0s represent water, return the number of islands. An island is covered with water horizontally or vertically, not diagonally. ex. Input: grid = [ [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1] ] Output: 3 --------------------------------------------------------------------------------- public int method (char[][] grid) { .... }

    Approach: The trick is to call a helper method recursively, where it changes the spaces around the island in-place to '2's. In the main method, get the number of rows and columns, and save the count as 0. In a double for-loop for rows and columns, check if that space is a '1'. If it is, then increase the count and call the helper method. We can do this since the helper method will change the spaces around it in-place to '2's. In the helper method, check if the index is out of bounds for the row…

69. 130. Surround Regions Given an m*n char grid called board, which contains some 'X's and 'O's, replace all regions of 'O's that are completely surrounded by 'X's horizontally and vertically with 'X's. Regions of 'Os' that touch the border do not count. ex. Input: board = [ [X, X, X, X], [X, O, O, X], [X, X, O, X], [X, O, X, X] ] Output: [ [X, X, X, X], [X, X, X, X], [X, X, X, X], [X, O, X, X] ] --------------------------------------------------------------------------------- public void method (…

    Approach: The trick is to call a helper method recursively, where it changes spaces on the border only in-place to 'E's. In the main function, get the number of rows and columns in the board. In a for-loop for the number of columns, call the helper method on the first and last row. Then, in a for-loop for the number of rows, call the helper method on the first and last columns. Then, in a double for-loop, change all remaining 'O's to 'X's, and change all 'E's to 'O's as well. In the helper meth…

70. 133. Clone Graph Given a node in an undirected graph, return a deep copy (a clone) of the graph. A node object will have a value and a list of node neighbors. ex. Input: list = [ [2, 4], [1, 3], [2, 4], [1, 3] ] Output: [ [2, 4], [1, 3], [2, 4], [1, 3] ] --------------------------------------------------------------------------------- public Node method (Node node) { .... } class Node { ....public int val; ....public List<Node> neighbors; ....public Node(int val, ArrayList<Node> neighbors) { ..…

    Approach: The trick is to use a breadth-first search to go through the neighbors of each node. First, create a HashMap where key=original node and value=cloned node, where this map keeps track of duplicates to prevent infinite cycles. Put the first node into the map. Also create a Queue to do breadth-first search. While the queue is not empty, poll the queue and go through that node's list of neighbors. If the map does not include that neighbor yet, add that original neighbor to the map and the…

71. 167. Two Sum (Part 2) Given a sorted int array numbers in increasing order, return the indices of 2 numbers that add up to a target number. Return both indices added by 1 (say the array is 1-indexed instead of 0-indexed, so it starts at 1). There will always only be one solution. ex. Input: numbers = [2, 7, 11, 15], and target = 9 Output: [1, 2] --------------------------------------------------------------------------------- public int[] method (int[] numbers, int target) { .... }

    Approach: Unlike the regular two-sum problem (where you used a HashMap to keep track of indices), this array is already sorted, so use a 2 pointer approach instead. Save 2 pointers at the start and end of the array. While left < right, add the values at the indices together. If the sum is equal to the target, return the 2 indices plus one. If the sum is less than the target, increase left. If the sum is greater than the target, decrease right. Code: public int[] method (int[] numbers, int targe…

72. 739. Days Until Warmer Temperature Given an int array temperatures, return a new int array where array[i] represents the number of days to wait until the temperature is a higher number. ex. Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73] Output: [1, 1, 4, 2, 1, 1, 0, 0] --------------------------------------------------------------------------------- public int[] method (int[] temperatures) { .... }

    Approach: First, save the length of the array, and create a new rtn array. Then, create a Stack (or Deque) object to keep track of the previous indices of highest temperatures. In a for-loop from the last index of the array to 0 (inclusive), use a while-loop to pop from the stack while the stack is not empty and the temperature at index i is higher than the temperature at index stack.peek(). Then, if the stack is not empty, set the value of the rtn array to stack.peek() - i, which gets the days…

73. 605. Can Place Flowers Given an int array flowerBed, where 0 means there is no flower there and 1 means there is a flower there, return true if n flowers can be planted, where no flowers can be placed next to each other. ex. Input: flowerbed = [1, 0, 0, 0, 1], and n = 2 Output: false --------------------------------------------------------------------------------- public boolean method (int[] flowerbed, int n) { .... }

    Approach: We will be editing the array in-place. Save variables for the count and the length of the array. In a for-loop for the length of the array, if the value at the index is 0, then create 2 boolean variables: 1 for if the previous index was 0 (or if the previous index is i=0) and 1 for if the next index is 0 (or if the next index is the last index). If both of them are true, then set the value at that index to 1 and return the count. If the count >= n, then we can just return true. Outsid…

74. 209. Smallest Subarray That Adds Up to Target Given a positive int array nums and an int target, return the length of the smallest array that is greater than or equal to the target (or 0 if there is none). ex. Input: nums = [2, 3, 1, 2, 4, 3], and target = 7 Output: 2 ([4, 3]) --------------------------------------------------------------------------------- public int method (int target, int[] nums) { .... }

    Approach: Use a sliding window approach. Create 3 variables: 1 for the current sum, 1 for the left pointer, and 1 for the length of the window to return (initialized as the length of the array + 1 since we will never reach this value, telling us if we never find a long enough subarray). In a for-loop for the length of the array, add the value at that index to the sum. In a while-loop while the sum is greater than or equal to the target, calculate the current window length (i - left + 1) and upd…

75. 3. Longest String Without Repeating Characters Given a string s, return the length of the longest substring without repeating characters. ex. Input: s = "abcabcbb" Output: 3 --------------------------------------------------------------------------------- public int method (String s) { .... }

    Approach: Use a sliding window approach. Keep track of 3 variables: 1 to keep track of the start index of the sliding window, 1 to keep track of the longest string length, and 1 as a HashMap where key=character and value=index to keep track of the last position of each character. In a for-loop for the length of the string, get the character at that index. If the map already contains that key, update the start variable to Math.max() of either the current start variable or just map.get(c)+1 (whic…

76. 1408. Finding All Substrings Given a String array words, return all of the words in the array that are a substring of any of the other words in the array (return the smaller words, not the larger words). ex. Input: words = ["mass", "as", "superhero", "hero"] Output: ["as", "hero"] --------------------------------------------------------------------------------- public List<String> method (String[] words) { .... }

    Approach: Create an ArrayList to keep track of the substrings to return. In 2 double for-loops for the length of the array, first continue if i == j. Then, check if one string contains the other. If so, add the shorter string to the list and break out of the inner for-loop. Code: public List<String> method (String[] words) { ....List<String> list = new ArrayList<>(); ....for (int i = 0; i < words.length; i++) { ........for (int j = 0; j < words.length; j++) { ............if (i == j) ...........…

77. 3042. Count Prefix and Suffix Pairs Given a String array words, return the number of pairs where words[i] is a prefix and suffix of words[j], where i occurs in the array before j. ex. Input: words = ["a", "aba", "ababa", "aa"] Output: 4 (1: 'a' and 'aba') (2: 'a' and 'ababa') (3: 'a' and 'aa') (4: 'aba' and ababa') --------------------------------------------------------------------------------- public int method (String[] words) { .... }

    Approach: First, save variables for the count to return, as well as the number of words in the array. Then, in a for-loop for the length of the array, save the word at index i, and get the length of that word. Then, in an inner for-loop starting at i+1 to the length of the array, save the word at index j, and get the length of that word. Make a check to continue if the length of the second word is shorter than the first word. Then, create a boolean variable for if the pair is valid. In a for-lo…

78. 13. Roman to Integer Given a Roman numeral, return it is a counting integer. There are 3 subtraction rules to keep in mind: I can be placed before V (5) and X (10) to make 4 and 9 X can be placed before L (50) and C (100) to make 40 and 90 C can be placed before D (500) and M (1000) to make 400 and 900 I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000 ex. Input: s = "MCMXCIV" Output: 1994 (M = 1000) (CM = 900) (XC = 90) (IV = 4) -----------------------------------------------------------------…

    Approach: First, create a map of all of the Roman numerals, where key=Roman numeral and value=number. Then, create 2 variables: 1 for the value to return, and 1 keeping track of the last seen countable number, going from right to left (ex. 100, 10). In a for-loop from the end of the array to 0 inclusive, get the countable number from the map. If this number is less than the previous value (ex. CM = 100 1000), then subtract that number from the sum. If not, add it to the sum. Set the previous va…

79. 1400. Can You Construct N Palindromes Given a String s and an integer k, return true if you can use ALL of the characters in s to construct k palindrome strings. ex. Input: s = "annabelle", k = 2 Output: true (ex. anna + elble) (ex. anbna + elle) (ex. anellena + b) --------------------------------------------------------------------------------- public boolean method (String s, int k) { .... }

    Approach: The trick is to look at how many characters show up an odd number of times, where if the odd count is greater than k (i.e. each odd character will have to be its own palindrome), then return false. Also consider if k is less than the length of the string. Code: public boolean method (String s, int k) { ....if (k > s.length()) ........return false; ....int[] array = new int[26]; ....for (char c: s.toCharArray()) ........array[c - 'a']++; ....int odd = 0; ....for (int i : array) { .....…

80. 2116. Check if Parentheses String Can Be Valid Say you're given a String s and a String locked. s contains only open and closed parentheses '(' and ')'. s is considered valid if all open parentheses are eventually closed. locked contains only '0's and '1's. If locked[i] is 0, then you can change s[i] to either an open or closed parentheses. If locked[i] is 1, then you can't. Return true if you can make s valid. NOTE: You don't need to make s valid. Just return true if it can be. ---------------…

    Approach: First, return false if the string's length is odd. Then, create 2 variables: 1 to check the difference between how many open and closed parentheses there are (balance), and 1 to keep track of how many '0' positions there are (canModify). Create 2 for-loops: 1 going left to right, and 1 going right to left. In each loop, increase canModify if we're at a 0. Otherwise, update the balance, where in the first for-loop going left to right, increase balance for each OPEN parentheses '(' whic…

81. 3223. Length of String After Removal Operations Given a String s, do the following operation as many times until you end up with the shortest string: for any given index in s[i], if that character value is present to the left AND right sides of the string, then remove the left and right instances. Note that it must be present on both sides, not just one. The string will only contain lowercase letters. Return the length of the remaining string. public int method (String s) { .... }

    Approach: The trick is that we don't actually need to change the String. Just create a character array of size 26 to keep track of the frequencies of each character. Create a sum variable to return. Then, in a for-loop of the array, if the frequency is even, then add 2 to the sum (ex. 'aaaaaa' -> 'aa' at the end). If the frequency is even, then add 1 to the sum (ex. 'bbb' -> 'b'). Code: public int method (String s) { ....int[] array = new int[26]; ....for (char c : s.toCharArray()) ........arra…

82. 2657. Array Containing Number of Prefix Values in Common You are given 2 int arrays A and B, which have the same numbers but in different orders (ex. [3, 1, 2] and [2, 3, 1]). Return an int[] array where the value at array[i] is the number of numbers that both arrays have in common up to index i. ex. Input: A = [1, 3, 2, 4] and B = [3, 1, 2, 4] Output: [0, 2, 3, 4] (at index 0, they have no numbers in common) (at index 1, they have 1, 3 in common) (at index 2, they have 1, 2, 3 in common) (at i…

    Approach: Create 2 HashSets, and create an int array to return. Save the count variable for the number of numbers in common too. In a for-loop, check if setA contains the value at A[i] already. If it does, do not do anything. If not, add it to the set, and then increase count if setB also has that value. Do the same vice versa for setB. Then, set the value at the return index to the count. Code: public int[] method (int[] A, int[] B) { ....HashSet<Integer> setA = new HashSet<>(); ....HashSet<In…

83. 2300. Number of Successful Spell-Potion Pairs Given an integer success and 2 unsorted int[] arrays spells and potions, where spells[i] and potions[j] represents the strength of each spell or potion, return an int[] array of length spells.length, where rtn[i] is the number of potions that will successfully create a spell. It is a success if spells[i] * potions[j] is at least success. ex. Input: spells = [5, 1, 3] and potions = [1, 2, 3, 4, 5] and success = 7 Output: [4, 0, 3] -------------------…

    Approach: Use a binary search approach. First, sort the potions array, save the lengths of both arrays, and create a rtn array. In a for-loop, you want to create a target variable, representing the smallest number needed to multiply with spells[i] to get success. This is done with a clever trick (success + spells[i] - 1 / spells[i]), which should just be memorized (do not use Math.ceil). Then, call a helper binary search method with the potions array and that target value, and save the index re…

84. 1266. Minimum Time to Visit All Coordinates Say you are given a 2D int[][] array called points. Return the minimum time it takes to visit all points in order. In one second you can move either one space vertically, horizontally, or diagonally. ex. Input: [ [1,1], [3,4], [-1,0] ] Output: 7 --------------------------------------------------------------------------------- public int method (int[][] points) { .... }

    Approach: The trick is that you don't actually need to manually move each point. Instead, the amount of spaces to move from one coordinate to the next is the Math.max() of whichever is greater: traveling across the x-axis or the y-axis. Save a variable for the total to return. In a for loop up to the second to the last point, get the x-coordinates and y-coordinates of the current and next coordinate. Get their absolute values of their differences, and add whichever value is larger to the total.…

85. 896. Monotonic Array Given an int[] array nums, return true if all of the values are either increasing or decreasing, but never both. Staying the same value is fine too (ex. [3, 3]). ex. Input: nums = [1, 2, 2, 3] Output: true --------------------------------------------------------------------------------- public boolean method (int[] nums) { .... }

    Approach: Have 2 boolean values for if the array is increasing or decreasing, and set both to false. In a for-loop starting at 1, update the variables comparing nums[i] to nums[i-1]. Return false if both increasing and decreasing are ever true. Code: public boolean method (int[] nums) { ....if (nums.length <= 2) ........return true; ....boolean increasing = false; ....boolean decreasing = false; ....for (int i = 1; i < nums.length; i++) { ........if (nums[i] < nums[i-1]) ............decreasing…

86. 2765. Longest Alternating Subarray Given an int[] array nums, return the length of the longest array where nums[i+1] == nums[i] + 1, and the sequence alternates like (s0, s1, s0, s1, etc.). ex. Input: nums = [2, 3, 4, 3, 4] Output: 4 ([3, 4, 3, 4]) --------------------------------------------------------------------------------- public int method (int[] nums) { .... }

    Approach: Save a variable for the maximum length to return. In a for-loop to the length of the array - 1, save the values at nums[i] and nums[i+1]. If the second value is not the first + 1, just continue. Otherwise, save the current length of this subarray (2) and the index to start checking values at (start + 2). In a while-loop while this index is less than the length of the array, get the expected value for either the first or second value (based on the current LENGTH of the subarray), updat…

87. 2610. Turn 1D Array to 2D Array Without Duplicates Given an int[] array nums, create a 2D array where each row in the array does not contain any duplicates numbers. There should be as minimum rows in the 2D array as possible. Note that the numbers do not have to be added in order, and the numbers range from 1 to 200. ex. Input: nums = [1, 3, 4, 1, 2, 3, 1] Output: [ [1, 3, 4, 2], [1, 3], [1] ] --------------------------------------------------------------------------------- public List<List<Int…

    Approach: The trick is to create a frequency array keeping track of how often each number shows up. From there, create a boolean value that tells you if any of the values in frequency are still greater than 0 (you'll be decreasing each value by 1 with each pass), and in a while-loop while that boolean value is true, this iteration represents one new row in the 2D array. Immediately set that boolean value to false (it'll be reset to true if we have to create a new row). In a for-loop from 1 to t…

88. 2869. Minimum Operations to Get Elements 1 to K Given an ArrayList<Integer> nums of positive integers, say with one iteration, you can remove the last element and save it to a temporary collection. Say you are also given an integer k. Return the minimum number of operations to collect elements 1, 2, ... up to k. ex. Input: nums = [3, 1, 5, 4, 2], and k = 2 Output: 4 (We collect 2, then 4, then 5, then 1. We only need to collect up to k, so 1 and 2). ---------------------------------------------…

    Approach: Create a new HashSet of numbers from 1 to k. In a for-loop starting from the end of the list to 0 inclusive, remove the value at that index of the list from the set, and increase the count. Break out of the loop when the set is empty, meaning all of the needed numbers are collected. Code: public int method (List<Integer> nums, int k) { ....Set<Integer> set = new HashSet<>(); ....for (int i = 1; i <= k; i++) ........set.add(i); ....int rtn = 0; ....for (int i = nums.size() - 1; i >= 0;…

89. 1765. 2D Array of Highest Peak Given a 2D int[][] array isWater, where 0 is land and 1 is water, return a new 2D array with values that fit the following rules: Water cells should be 0 Adjacent cells (directly next to, NOT diagonally) should have a difference of at most 1 The array's maximum value should be in the array. ex. Input: [ [0, 0, 1], [1, 0, 0], [0, 0, 0] ] Output: [ [1, 1, 0], [0, 1, 1], [1, 2, 2] ] --------------------------------------------------------------------------------- pub…

    Approach: Use a breadth-first search approach with a Queue. First, save the number of rows and columns in the 2D array. Create a returning 2D array of those dimensions, and create a queue as well of type int[] to store the 'coordinates' (ex. [1, 2]). In a double for-loop, replace all land instances with -1 (marking them as unvisited), and mark all water instances with 0 AND add that coordinate to the queue. Create an int[][] containing directions for adjacent cells (ex. [-1, 0], [0, 1], etc.).…

90. 1267. Number of Servers Connected to Another Server You are given a 2D int[][] array grid, where 0 means there is no server there, and 1 means there is a server there. 2 servers are connected if they are on the same row or column. Return the number of servers that can communicate with any other server. This does not necessarily mean that all of the servers have to be connected to one another. ex. Input: Output: 4 ---------------------------------------------------------------------------------…

    Approach: Save the number of rows and columns, and create 2 arrays, each representing the number of servers in a row or column. In a double for-loop, keep track of how many servers are in a row or column. The idea is that for a server to be connected, its value should be 1, and then either its row or column in the corresponding array should be 2 or higher (not 1 since 1 just represents itself). Code: public int method (int[][] grid) { ....int rows = grid.length; ....int cols = grid[0].length; .…

91. 2150. Find "Lonely Numbers" Given an int[] array nums, return all "lonely numbers", which is a number in the array which only appears once AND the numbers 1 above and 1 below do not appear in the array. ex. Input: nums = [10, 6, 5, 8] Output: [10, 8] --------------------------------------------------------------------------------- public List<Integer> method (int[] nums) { .... }

    Approach: Create a HashMap where key=number and value=frequency. Iterate through the input array to record the frequency of each number. Create a list to return. Iterate through the entrySet of the map. Only add the value if the keys 1 above and 1 below do not appear, as well as if the value is only 1. Code: public List<Integer> method (int[] nums) { ....Map<Integer, Integer> map = new HashMap<>(); ....for (int num : nums) ........map.put(num, map.getOrDefault(num, 0) + 1); ....List<Integer> rt…

92. 48. Rotate Matrix 90 Degrees Given an n x n matrix, rotate the image 90 degrees clockwise in-place, meaning you have to modify the input matrix directly instead of creating another 2D matrix. ex. matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] Output: [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ] --------------------------------------------------------------------------------- public void rotate (int[][] matrix) { .... }

    Approach: The trick is instead of directly rotating the array, you do 2 linear algebra operations: transposing the array across the diagonal line y = -x, and then you reverse each row. Code: public void rotate (int[][] matrix) { ....int n = matrix.length; ....for (int i = 0; i < n; i++) { ........for (int j = i; j < n; j++) { ............int temp = matrix[i][j]; ............matrix[i][j] = matrix[j][i]; ............matrix[j][i] = temp; ........} ....} ....for (int i = 0; i < n; i++) { ........in…

93. 997. Find the Town Judge You are given a 2D int[][] array, where a value trust[i] will be [a, b], where a "trusts" b. The rules are that the town judge trusts no one, and everyone trusts the town judge. You are also given an int n, where there will be n people labeled 1 to n. Return the town judge if they exist, or -1 if they do not exist. ex. Input: n = 3, trust = [ [1,3], [2,3] ] Output: 3 --------------------------------------------------------------------------------- public int method (int…

    Approach: Create 2 arrays of size n+1 (since we start at index 1), which indicate the how many people that index i trust and how many people trust index i. In a for-each loop of trust, increase the corresponding values in the array. Then in a for-loop from index 1 to n inclusive, check if index i trusts no one and everyone trusts index i. Code: public int method (int n, int[][] trust) { ....int[] trusts = new int[n + 1]; ....int[] trusted = new int[n + 1]; ....for (int[] pair : trust) { .......…

94. 763. Partition This String You are given a String s. You want to divide this string into as many parts as possible, where all of the characters in any part are only found in that part and no other parts. You cannot change the order of the characters in the string. Return a list of integers representing the size of these parts. ex. Input: s = "ababcbacadefegdehijhklij" Output: [9, 7, 8] ('ababcbaca', 'defegde', 'hijhklij') -------------------------------------------------------------------------…

    Approach: Create an int[] of size 26, where each value represents the LAST index that we see each character a-z. We'll keep track of 2 other variables: start and end, representing the start and end of partitions, both initialized at 0. In a for-loop for the length of the string, update the value of end to be Math.max of end and the last index of the current character (by checking the array). The idea is that if i == end, then this means that we've reached the end of the partition, so add it to…