Session 18: HashMap & Two Pointers

Original Session

Date: 15 Dec 2024

Topic: Two Pointers

Concept: Hash Map

Concept: Two Pointers

Concept:

consider start, i and j index in array.

sum from start to i = Sum

sum of start to j = Sum

which means sum from i to j = 0;

HomeWork: https://leetcode.com/problems/minimum-area-rectangle/description/

Programs

1. Number of occurrence
   1. GFG here

   int countFreq(int[] arr, int target) {
           // code here
           
           Map<Integer, Integer> map = new HashMap();
           
           for (int value : arr) {
               
               map.put(value, map.getOrDefault(value, 0) + 1);
           }
           
           return map.getOrDefault(target, 0);
       }

2. Print frequency of each occurrence
   1. Not on any portal

   void freq(int[] arr) {
           // code here
           
           Map<Integer, Integer> map = new HashMap();
           
           for (int value : arr) {
               
               map.put(value, map.getOrDefault(value, 0) + 1);
           }
           
   				for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
   					System.out.println(entry.getKey() + " : " + entry.getValue());
   				}
       }

3. Array Subset
   1. GFG here

   Map<Integer, Integer> map = new HashMap();
           for (int value: a) {
               map.put(value, map.getOrDefault(value, 0) + 1);
           }
           
           for (int value: b) {
               
               if (!map.containsKey(value)) {
                   return false;
               }
               
               int occurence = map.get(value);
               if (occurence == 0) {
                   return false;
               }
               map.put(value, occurence - 1);
           }
           
           return true;

4. Valid Anagram
   1. leetocode here

   public boolean isAnagram(String s, String t) {
           
           if (s.length() <= 0 || t.length() <= 0) {
               return false;
           }
   
           if (s.length() != t.length()) {
               return false;
           }
   
           Map<Character, Integer> hashMap = new HashMap();
   
           for (Character ch: s.toCharArray()) {
   
               if (!hashMap.containsKey(ch)) {
                   hashMap.put(ch, 1);
                   continue;
               }
   						hashMap.put(ch, hashMap.get(ch) + 1);
           }
   
           for (Character ch: t.toCharArray()) {
   
               if (!hashMap.containsKey(ch)) {
                   return false;
               }
   
               int newCount = hashMap.get(ch) - 1;
               if (newCount <= 0) {
                   hashMap.remove(ch);
                   continue;
               }
   
               hashMap.put(ch, newCount);
           }
   
           return true;
       }

5. Subarray with 0 sum
   1. GFG here

   boolean findsum(int arr[]) {
           // Your code here
           
           int sum = 0;
           int ans = 0;
           Map<Integer, Integer> map = new HashMap();
           for (int i=0; i< arr.length; i++) {
               
               sum += arr[i];
               
               if (sum == 0) {
               ans = i + 1;
               continue;
           }
           
           if (!map.containsKey(sum)) {
               map.put(sum, i);
               continue;
           }
           
           ans = Math.max(ans, i-map.get(sum));
           }
           
           return ans > 0;
       }

6. Largest subarray with 0 sum
   1. GFG here

   int maxLen(int arr[]) {
           
           int sum = 0;
           int ans = 0;
           Map<Integer, Integer> map = new HashMap();
           for (int i=0; i< arr.length; i++) {
               
               sum += arr[i];
               
   		        if (sum == 0) {
   			          ans = i + 1;
   			          continue;
   				    }
   		        
   		        if (!map.containsKey(sum)) {
   		            map.put(sum, i);
   		            continue;
   		        }
   		        
   		        ans = Math.max(ans, i-map.get(sum));
           }
           
           return ans;
       }

7. Subarrays with sum K
   1. GFG here

   public int findSubArraySum(int k, int nums[]) {
           
           int sum = 0, ans = 0;
           HashMap<Integer, Integer> map = new HashMap<>();
           map.put(0, 1);
   
           for (int i = 0; i < nums.length; i++) {
               sum += nums[i];
   
               if (map.containsKey(sum - k)) {
                   ans += map.get(sum - k);
               }
   
               map.put(sum, map.getOrDefault(sum, 0) + 1);
           }
   
           return ans;
           
       }

8. Subarray Sum Equals K
   1. leetocode here

   public int subarraySum(int[] nums, int k) {
           
           Map<Integer, Integer> map = new HashMap();
   
           int sum = 0, ans = 0;
           map.put(sum , 1);
   
           for (int i=0; i< nums.length; i++) {
   
               sum += nums[i];
   
               if (map.containsKey(sum-k)) {
                   ans += map.get(sum-k);
               }
   
               map.put(sum, map.getOrDefault(sum, 0) + 1);
           }
   
           return ans;
   
       }

9. 525. Contiguous Array
   1. leetocode here

   public int findMaxLength(int[] arr) {
   
           int sum = 0;
           int ans = 0;
           Map<Integer, Integer> map = new HashMap();
           for (int i=0; i< arr.length; i++) {
               
               sum += arr[i] ==0 ? -1 : arr[i];
               
   		        if (sum == 0) {
   			          ans = i + 1;
   			          continue;
                   }
   		        
   		        if (!map.containsKey(sum)) {
   		            map.put(sum, i);
   		            continue;
   		        }
   		        
   		        ans = Math.max(ans, i-map.get(sum));
           }
           
           return ans;   
       }