2 Pointer

4 flashcards · Other · by Steven Bui

1. 11. Hold the Most Water Given an int array height, where the value at height[i] represents the potential height of one side of a water container, return the maximum amount of water that can be held by the container. ex. Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (8 at index 1, and 7 at index 8, maximum area is 7 * 7 = 49) ---------------------------------------------------------------------------------- public int method (int[] height) { .... }

   Approach: First, initialize 2 pointers: left to keep track of index 0, and right to keep track of the last index. Also create 2 variables to keep track of the maximum area and the minimum height. In a while-loop while left is less than right, calculate a variable called width, which is the distance between left and right. Update minHeight to be the shortest height between left and right. Then, get the current area (width * minHeight) and update the maximum area variable if a new maximum is foun…

2. 58. Length of Last Word Given a string s containing words and spaces, give the length of the last word. ex. Input: s = "fly me to the moon" Output: 4 (moon is 4 letters) ---------------------------------------------------------------------------------- public int method (String s) { .... }

   Approach: Save a variable i at the last index. First, make a while-loop that decreases i while you are at whitespace. Then, now that you are on a normal word, create a new variable length and increase it while the index is not on whitespace. Code: public int lengthOfLastWord(String s) { ....int length = 0; ....int i = s.length() - 1; ....while (i >= 0 && s.charAt(i) == ' ') ........i--; ....while (i >= 0 && s.charAt(i) != ' ') { ........i--; ........length++; ....} ....return length; } Time com…

3. 15. All Triplets That Add Up to 0 Given an int array nums, return an ArrayList of all combinations of triplets (3 numbers) that add up to 0. The numbers in a triplet can be the same, but obviously all numbers should have different indices. There should also be NO duplicate triplets. ex. nums = [-1, 0, 1, 2, -1, -4] Output: [ [-1, -1, 2], [-1, 0, 1] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (int[] nums) { .... }

   Approach: First, create a List<List<Integer>> to store the triplets. Then, sort the array using Arrays.sort(). Create a for-loop that goes up to nums.length - 2 since we will be using a 2 pointer approach: make index i be the current index, and left will point to the index right in front of i, and right will point to the index at the end of the array. In this for-loop, first skip all duplicates of i. Then, set left and right accordingly. Still inside of the for-loop, while left < right, check w…

4. 392. Is Subsequence Given 2 strings s and t, return true if the string s can be made by removing some of the characters in t without changing the order of the characters. ex. s = "ace", and t = "abcde" Output: true ---------------------------------------------------------------------------------- public boolean method (String s, String t) { .... }

   Approach: You are going to want to use the 2 pointer approach, where one index keeps track of sIndex and one index keeps track of tIndex. In a while-loop while tIndex is not at t.length, check if the characters at sIndex and tIndex are the same. If so, increment sIndex, and return true if sIndex is at s.length. Increment tIndex whether it is true or not. Code: public boolean method (String s, String t) { ....if (s.length() == 0) ........return true; ....int sIndex = 0; ....int tIndex = 0; ....w…