Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. Example: Input: n = 2 Output: ["11","69","88","96"] Solution # Time: O(n^2 * 5^(n/2)) # Space: `O(n)` class Solution: def findStrobogrammatic(self, n: int) -> List[str]: stroboPairs = { "0": "0", "1": "1", "6": "9", "8": "8", "9": "6" } return self.build(stroboPairs, n, n) def build(self, stroboPairs, curr, n): if curr == 0: return [""] if curr == 1: return list("018") prev = self.

by lek tin in "algorithm" access_time 1-min read

Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string. Example 1 Input: "69" Output: true Example 2 Input: "88" Output: true Example 3 Input: "962" Output: false Solution class Solution: def isStrobogrammatic(self, num: str) -> bool: pairs = { 1: 1, 6: 9, 8: 8, 9: 6, 0: 0 } mid = len(num)//2+1 for i in range(mid): leftNum = int(num[i]) rightNum = int(num[-i-1]) if leftNum not in pairs or pairs[leftNum] !

by lek tin in "algorithm" access_time 1-min read

Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1.

by lek tin in "algorithm" access_time 1-min read

Verifying an Alien Dictionary

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language. Example 1 Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

by lek tin in "algorithm" access_time 2-min read

Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1 «««< HEAD dev Input:nums = [1,1,1], k = 2 Output: 2 Note The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

by lek tin in "algorithm" access_time 2-min read

Find in Mountain Array

(This problem is an interactive problem.) You may recall that an array A is a mountain array if and only if: A.length >= 3 There exists some i with 0 < i < A.length - 1 such that: A[0] < A[1] < ... A[i-1] < A[i] A[i] > A[i+1] > ... > A[A.length - 1] Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target.

by lek tin in "algorithm" access_time 2-min read

Peak Index in a Mountain Array

Let’s call an array A a mountain if the following properties hold: A.length >= 3 There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.

by lek tin in "algorithm" access_time 1-min read

Sum of Square Numbers

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c. Example 1 Input: 5 Output: True Explanation: 1 * 1 + 2 * 2 = 5 Example 2 Input: 3 Output: False Solution import math class Solution: def judgeSquareSum(self, c: int) -> bool: if c <= 1: return True sqrt = math.ceil(math.sqrt(c)) left, right = 0, sqrt-1 while left*left + right*right < c: if (left+1)*(left+1) + right*right > c: right -= 1 else: left += 1 if left*left + right*right == c: return True return False Without sqrt function

by lek tin in "algorithm" access_time 1-min read

Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False. Note Do not use any built-in library function such as sqrt. Example 1 Input: 16 Output: true Example 2 Input: 14 Output: false Solution (naive) Java class Solution { public boolean isPerfectSquare(int num) { if (num == 1) return true; for (int i = 2; i < num; i++) { if (i * i == num) { return true; } if (i * i > num) { break; } } return false; } } Solution (Binary Search version 1) Let x be the square root, 1 < x < num/2 always holds true.

by lek tin in "algorithm" access_time 2-min read

Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower. However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

by lek tin in "algorithm" access_time 2-min read