• Array
• String
• Binary Search
• HashMap

Array

1. Rotate Elements by K
   1. remember: normalize k first and then reverse 3 times
   2. Right rotation by K:
      1. Reverse entire array
      2. Reverse the first ‘k’ elements
      3. Reverse the rest (from k to end)
   3. Left rotation by K:
      1. Reverse the first ‘k’ elements
      2. Reverse the rest (from k to end)
      3. Reverse entire array
   Code

   fun rotate(nums: IntArray, kk: Int): Unit {
       val n = nums.size
       val k = kk%n
       reverse(nums,0,n-1)
       reverse(nums,0,k-1)
       reverse(nums,k,n-1)
   }
   
   fun reverse(nums: IntArray, s: Int, e: Int){
       var start = s
       var end = e 
       while(start<end){
           nums[start] = nums[end].also { nums[end] = nums[start]}
           start++
           end--
       }
   }
   

2. *Contains Duplicate
   1. Brute Force: Use Two loops
      1. TC: O(N^2)
   2. Better: Sort()
      1. TC: O(N*logN)
   3. Optimal: HashSet or HashMap
      1. TC: O(N), SC: O(N)
3. Search in Rotated Sorted Array
   1. Use binary search and keep moving start and end based on sorted part conditions
   Code

   fun search(nums: IntArray, x: Int): Int {
       var n = nums.size
       var start = 0
       var end = n-1
       while(start<=end){
           val mid = (start+end)/2
           if(nums[mid]==x) return mid
           if(nums[start]<=nums[mid]){
               //left half is sorted
               if(nums[start]<=x && x<nums[mid]){
                   //element is sorted part
                   end = mid-1
               }else{
                   start = mid+1
               }
           }else{
               //right half is sorted
               if(nums[mid]<x && x<=nums[end]){
                   //element is sorted part
                   start = mid+1
               }else{
                   end = mid-1
               }
           }
       }
       return -1
   }
   

4. *Insert Interval
   1. Optimal:
      1. Add all intervals ending before newOne start
      2. Merge the overlapping ones
      3. Add the rest left over intervals
   Code

   fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
       var n = intervals.size
       val ans = mutableListOf<IntArray>()
       //add intervals ending before newOne 
       var i = 0
       while(i<n && intervals[i][1]<newInterval[0]){
           ans.add(intervals[i])
           i++
       }
       //merge the overlapping ones
       var start = newInterval[0]
       var end = newInterval[1]
       while(i<n && intervals[i][0]<=end){
           start = minOf(intervals[i][0],start)
           end = maxOf(intervals[i][1],end)
           i++
       }
       ans.add(intArrayOf(start,end))
       //add the rest intervals
       while(i<n){
           ans.add(intervals[i])
           i++
       }
       return ans.toTypedArray()
   }
   

5. Non-overlapping Intervals
   1. Optimal:
      1. Sort by end
      2. Create pairEnd and update it based on if(intervals[0] >= pairEnd)
   Code

   fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
       intervals.sortBy { it[1] }
       var count = 0
       var pairEnd = Int.MIN_VALUE
       for(interval in intervals){
           if(interval[0]>=pairEnd){
               pairEnd = interval[1]
           }else{
               count++
           }
       }
       return count
   }
   

6. Product of Array Except Self
   1. Optimal:
      1. Create Prefix Array, & Postfix Array
      2. Merge them to create Output Array
      3. TC: O(3N), SC: O(2N) (excluding output array)
   2. Optmial More:
      1. Create output array, store Prefix product first and then update with PostFix
      2. TC: O(2*N), SC: O(1)
   Code

   fun productExceptSelf(nums: IntArray): IntArray {
       var n = nums.size
       var output = IntArray(n)
       var prefix = 1
       for(i in 0 until n){
           output[i] = prefix
           prefix *= nums[i]
       }
       var postfix = 1
       for(i in n-1 downTo 0){
           output[i] *= postfix
           postfix *= nums[i]
       }
       return output
   }
   

7. Container With Most Water
   1. Use Two pointers, start and end and fetch height of left and right
   2. store max in ans=maxOf(ans, (end-start)*minOf(left,right))
   Code

   fun maxArea(height: IntArray): Int {
       var start = 0
       var end = height.size-1
       var ans = 0
       while(start<end){
           var left = height[start]
           var right = height[end]
           ans = maxOf(ans, (end-start)*minOf(left,right))
           if(left>right){
               end--
           }else{
               start++
           }
       }
       return ans
   }
   

8. Daily Temperatures
   Code

   fun dailyTemperatures(arr: IntArray): IntArray {
       var n = arr.size
       var result = IntArray(n){0}
       var stack = Stack<Int>()
       for(i in arr.indices){
           while(stack.isNotEmpty() && arr[stack.peek()]<arr[i]){
               var index = stack.pop()
               result[index] = i-index
           }
           stack.push(i)
       }
       return result
   }
   

9. Next Greater Element I

Code

   fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
       val n = nums1.size
       var map = hashMapOf<Int,Int>()
       var stack = Stack<Int>()
       for(num in nums2){
           while(stack.isNotEmpty() && stack.peek() < num){
               map.put(stack.pop(), num)
           }
           stack.push(num)
       }
       for(i in nums1.indices){
           nums1[i] = map.getOrDefault(nums1[i], -1)
       }
       return nums1
   }

1. Next Greater Element II
   Code

   fun nextGreaterElements(nums: IntArray): IntArray {
       var stack = Stack<Int>()
       val n = nums.size
       var res = IntArray(n){-1}
       for(i in 0 until n*2){
           var curIndex = i%n
           while(stack.isNotEmpty() && nums[stack.peek()] < nums[curIndex]){
               var index = stack.pop()
               res[index] = nums[curIndex]
           }
           if(i<n){
               stack.push(curIndex)
           }
       }
       return res
   }
   

2. Grid Unique Paths II
   Code

   fun uniquePathsWithObstacles(grid: Array<IntArray>): Int {
       var row = grid.size
       var col = grid[0].size
       val arr = IntArray(col)
       arr[0] = 1
   
       for(i in 0 until row){
           for(j in 0 until col){
               if(grid[i][j]==1){
                   arr[j] = 0
               }else if(j>0){
                   arr[j] = arr[j] + arr[j-1]
               }
           }
       }
       return arr[col-1]
   }
   

3. Spiral Matrix
   Code

   fun spiralOrder(matrix: Array<IntArray>): List<Int> {
       var col = matrix[0].size
       var row = matrix.size
       var top = 0
       var left = 0
       var bottom = row-1
       var right = col-1
       var ans = mutableListOf<Int>()
       while(top<=bottom && left<=right){
           for(i in left..right)   ans.add(matrix[top][i])
           top++
           for(i in top..bottom)   ans.add(matrix[i][right])
           right--
           if(top<=bottom) {
               for(i in right downTo left)   ans.add(matrix[bottom][i])
               bottom--
           }
           if(left<=right) {
               for(i in bottom downTo top)   ans.add(matrix[i][left])
               left++
           }
       }
       return ans
   }
   

4. Move Zeroes
   1. remember: one index i for all items and one index nonZero for non-zero items
      Code

      fun moveZeroes(nums: IntArray): Unit {
          val n = nums.size
          var nonZero = 0
          for(i in nums.indices){
              if(nums[i]!=0){
                  nums[nonZero] = nums[i]
                  nonZero++
              }
          }
          for(i in nonZero..n-1){
              nums[i] = 0
          }
      }
      

5. Missing Number
   1. remember: cyclic sort or (expected sum - current sum)
      Code

      fun missingNumber(nums: IntArray): Int {
          val n = nums.size
          var i = 0
          while(i<n){
              val curInd = nums[i]
              if(curInd < n && nums[curInd] != nums[i]){
                  val temp = nums[curInd]
                  nums[curInd] = nums[i]
                  nums[i] = temp
              } else{
                  i++
              }
          }
          for(i in nums.indices){
              if(i != nums[i]) return i
          }
          return n
      }
      

      String

6. Palindrome String
   1. Two Pointers
      Code

        fun isPalindrome(str: String): Boolean {
            val s = str.lowercase()
            if(s.isEmpty()) return true
            var start = 0
            var end = s.length-1
            while(start<end){
                if(s[start].isLetterOrDigit().not()) {
                // if(s[start] < 'a' || s[start] > 'z') {
                    start++
                    continue
                }
      
                if(s[end].isLetterOrDigit().not()) {
                // if(s[end] < 'a' || s[end] > 'z'){
                    end--
                    continue    
                }
      
                if(s[start]==s[end]){
                    start++
                    end--
                }else{
                    return false
                }
            }
            return true
        }
      

   2. InBuilt
      Code

       fun isPalindrome(s: String): Boolean {
           val sanitized = s.filter { it.isLetterOrDigit() }.lowercase()
           return sanitized==sanitized.reversed()
       }
      

Binary Search

HashMap

###