LeetCode Problem : Palindrome Number

goosamsf — Thu, 28 Dec 2023 17:25:13 +0000

Problem Statement

Given an integer x, return true if x is a
palindrome, and false otherwise.

Intuition

How to revert integer number? How to approach this problem without even converting into string?

Approach

integer 121 for example,

121 / 10 = 12
121 % 10 = 1 , let this be 'a' 

12 / 10 = 1
12 % 10 = 2 , let this be 'b' 

1 / 10 = 0
1 % 10 = 1 , let this be 'c'

reverted number is (((a*10) + b)10 + c)

But here we want to revert only half because the range of the given input number is between -2^31 and 2^31. That is 2147483648 and if we try to revert this number entirely, int type can not even hold this value since the least significant digit is greater than the most significant digit. Therefore what we want to do is to revert only half of it. We can do this by making sure building-reverted number is less than the original number repeatly being divided by 10. For example, consider integer 1234, there will be comparison 4 vs 123 than 12 vs 43 and this is the exact condition we want to stop.

When the length of input is odd, we can simply do comparison between building-reverted number divided by 10 is equal to the original 'getting-smaller' number.

Lastly we want to handle following edge cases.
- Negative number -> always not palindrome
- 0 -> always palindrome
- number multiple of 10 -> always not palindrome

Time Complexity

O(log10 N) : Every iteration we divide the number by 10

Code

func isPalindrome(x int) bool {
    var rev int
    if x < 0 || (x % 10 == 0 && x!= 0){
        return false
    }
    if x < 10 {
        return true
    }

    for x > rev {
        rev = rev*10 + (x%10)
        x = x/10
    }
    if x == rev || rev/10 == x {
        return true
    }
    return false
}

Can We Do Better?

No, O(logN) is already good enough

Seed For Interview

Revert half of the number and be careful about few edge cases.

LeetCode Problem : Jump Game

goosamsf — Sun, 24 Dec 2023 19:09:20 +0000

LeetCode Problem : Jump Game

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Overview

Dynamic Programming can be used by iterating over array and check if the current index is reachable. However even with dynamic programming, it's still O(N^2). How to optimize this to O(N) where we only pass an array once : Greedy

Intuition

An index is reachable if you can jump from some of previous reachable index.

Approach

Construct boolean array reachable. Iterate over nums. for each index i check if ith index is reachable from any of reachable indices. We do this by checking all indices that marked as reachable from previous iteration. if reachable, set reachable[i] to true. Keep going upto last index and if last index of reachable true, return true, false otherwise.

Can we do better?

Think of you standing at the position and see which position is the furthest position you can jump to. Keep tracking of this information and do this at each position and at any index if the current index is bigger than position that you can jump furthest, return false. otherwise return true.

Code

//Dynamic Programming : O(N^2)
func canJump(nums []int) bool {
  //declare slice    
  reachable := make([]bool, len(nums))
  reachable[0] = true
  for i:=1; i< len(nums); i++ {
    for j := 0; j < i; j++ {
      if reachable[j] {
        if j+nums[j] >= i {
          reahcable[i] = true
          break
        }
      }
    }
  }
  return myslice[len(nums)-1]
}


func canJump(nums []int) bool {
    furthest:=0
    if len(nums)==1{ 
        return true
    }

    for i:=0;i<len(nums);i++{
        if i>furthest{
           return false
        }
        far=max(far, i+nums[i])
    }
    return true
}

Seed for Interview

Greedy : for each index i, if i is greater than furthest return false. Than compute furthest from i.

DEV Community: goosamsf

LeetCode Problem : Palindrome Number

Problem Statement

Intuition

Approach

Time Complexity

Code

Can We Do Better?

Seed For Interview

LeetCode Problem : Jump Game

LeetCode Problem : Jump Game

Problem Statement

Overview

Intuition

Approach

Can we do better?

Code

Seed for Interview