Session 1&2: Time complexity, Arrays & Maths

Original Session

Date: 2 Nov 2024

1. Sum of all Numbers in Array
   1. linear progression for O(1) - N/2 (a + l)
      Where N = count of numbers to add.
      a = start of the range of numbers.
      l = end of the range of numbers.
      
      

2. Sum of odd or even numbers in Array
   1. Same as 1.
      1. Sum even N/2(a + 2n), a= 2
      2. Odd N/2(a + 2n-1), a = 1
         
         

3. Reverse an Array.
   1. Two pointers.
      1. Left to first and Right to last element.
      2. Swap left and right, move left to right and right to left by one position.
         
         

4. Reverse array groups of K elements
   1. Reverse first K arrays in the array.
   2. then move the window by K elements to next group.
   3. If right ≥ N - 1 then consider right = N-1.
   4. Terminal condition if left > right;

Revision Session

Date: 6 Nov 2024

1. Find largest and second largest

2. Min and Second min.

3. Sum of digits of the number.
   1. modulo % and division /.
      1. code

      private static int test() {
              
              int index = 88022;
              int sum = 0;
              while (index > 0) {            
                  sum += index % 10;
                  index = index / 10;
              }
              
              return sum;
          }

   2. Swap two values
      1. use temp variable.
         
         
   3. Reverse array
      1. Two pointers swap left and right value.
         
         
   4. Reverse array in group of K
      1. code
         
         

      private static void reverseGroupK() {
              
              int[] arr = {1,2,3,1,2,3,1,2,3,1};
              int k = 3;
              int n = arr.length;
              
              int startWindow = 0;
              int endWindow = k - 1;
              
              while (startWindow < n) {
                  
                  int left = startWindow;
                  int right = endWindow;
                  
                  while (left < right) {
                      
                      int temp = arr[left];
                      arr[left] = arr[right];
                      arr[right] = temp;
                      
                      left ++;
                      right --;
                  }
                  
                  startWindow = endWindow + 1;
                  endWindow = startWindow + k - 1;
                  if (endWindow >= n) {
                      endWindow = n - 1;
                  }
              }
      
              System.out.println(Arrays.toString(arr));
          }

   5. 283. Move Zeroes leetocde
      1. sliding window
         
         

      private static void test() {
              
              int[] arr = {1,0,2,0,3,4};
              int n = arr.length;
              
              int count = 0;
              
              for (int i = 0; i < n; i++) {
                  
                  if (arr[i] != 0) {
                      arr[count] = arr[i];
                      count ++;
                  }
              }
              
              while (count < n) {
                  arr[count] = 0;
                  count ++;
              }
              
              System.out.println(Arrays.toString(arr));
              
          }

   6. Maximum SubArray
      1. leetcode 53.
         
         

      public int maxSubArray(int[] nums) {
              
              int max_sum = Integer.MIN_VALUE;
              int curr_sum = 0;
      
              for (int value : nums) {
      
                  curr_sum += value;
                  max_sum = Math.max(max_sum, curr_sum);
                  if (curr_sum < 0) {
                      curr_sum = 0;
                  }
              }
      
              return max_sum;
          }

   7. 724. Find Pivot Index .

      public int pivotIndex(int[] nums) {
              
              int leftSum = 0;
              int rightSum = 0;
              int total = 0;
      
              for (int value: nums) {
                  total += value;
              }
      
              for (int index = 0; index < nums.length; index ++) {
                  
                  int currentItem = nums[index];
                  rightSum = total - currentItem - leftSum;
                  if (leftSum == rightSum) {
                      return index;
                  }
                  leftSum += currentItem;
              }
      
              return -1;
          }

      1. 169. Majority Element leetocde.

         public int majorityElement(int[] nums) {
                 
                 int lead = 0;
                 int ans = 0;
         
                 for (int value : nums) {
         
                     if (lead == 0) {
                         ans = value;
                     }
         
                     if (value == ans) {
                         lead ++;
                     } else {
                         lead --;
                     }
                 }
         
                 return ans;
             }