Session 19: Two Pointers

Original Session

Date: 19 Dec 2024

Topic: Two Pointers

Concept:

Programs

1. 485. Max Consecutive Ones
   1. leetcode here

   public int findMaxConsecutiveOnes(int[] nums) {
           
           int ans=0, ones=0;
           int maxCount = 0;
   
           for (int i=0; i< nums.length; i++) {
   
               if (nums[i] == 1) {
                   ones++;
   
                   if (ones > ans) {
                       ans = ones;
                   }
               } else {
                   ones = 0;
               }
           }
   
           return ans;
       }

2. 1004. Max Consecutive Ones III
   1. leetcode here

   public int longestOnes(int[] nums, int k) {
           
           int i=0,j=0;
           int ans=0, flip=0;
           int n = nums.length;
   
           while (i < n) {
   
               if (nums[i] == 0) {
                   flip++;
               }
   
               while (flip > k) {
   
                   // unflip prev zero
   
                   if (nums[j] == 0) {
                       flip --;
                   }
                   j++;
               }
   
               ans = Math.max(ans, i-j+1);
               i++;
           }
   
           return ans;
       }

3. 3. Longest Substring Without Repeating Characters
   1. leetcode here

   public int lengthOfLongestSubstring(String s) {
           
           int n = s.length();
           int ans = 0;
           Map<Character, Integer> map = new HashMap();
   
           for (int j=0, i=0; j<n; j++) {
   
               if (map.getOrDefault(s.charAt(j),0) > 0) {
   
                   i = Math.max(i, map.getOrDefault(s.charAt(j), 0));
               }
   
               ans = Math.max(ans, j-i+1);
               map.put(s.charAt(j), j+1);
           }
   
           return ans;
       }

4. 904. Fruit Into Baskets
   1. leetcode here

   public int totalFruit(int[] fruits) {
           
           int left = 0, maxPicked=0, n=fruits.length;
   
           Map<Integer, Integer> basket = new HashMap();
   
           for (int right=0; right < n; right ++) {
   
               int rightFruit = fruits[right];
               basket.put(rightFruit, basket.getOrDefault(rightFruit, 0) + 1);
               while (basket.size() > 2) {
   
                   int leftFruit = fruits[left];
                   basket.put(leftFruit, basket.get(leftFruit) - 1);
                   if (basket.get(leftFruit) == 0) {
                       basket.remove(leftFruit);
                   }
                   left ++;
               }
               maxPicked = Math.max(maxPicked, right-left+1);
           }
           return maxPicked;
       }

5. 1423. Maximum Points You Can Obtain from Cards
   1. leetcode here

   public int maxScore(int[] cardPoints, int k) {
           
           int sum = 0;
           for (int i =0; i<k; i++) {
   
               sum += cardPoints[i];
           }
   
           int ans = sum;
           k--;
           int i = cardPoints.length - 1;
           while (k >= 0) {
               
               sum = sum - cardPoints[k] + cardPoints[i];
               k--;
               i--;
               ans = Math.max(ans, sum);
           }
   
           return ans;
       }