Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1 Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true Example 2 Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false Solution # Treat the 2-d matrix as a 1-d list of length rows * cols.

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

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1 Input: [1,3,4,2,2] Output: 2 Example 2 Input: [3,1,3,4,2] Output: 3 Note You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space.

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

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index. According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.” Example Input: citations = [3,0,6,1,5] Output: 3 Explanation [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.

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

Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

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

Invert Binary Tree

Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 Thoughts What if a node is NULL? A NULL has no children, so how to iterate deeper into the tree? Solution // Attempt // class Solution { // public: void swapNodes(*leftNode, *rightNode) { *temp = *leftNode; *leftNode = *rightNode; *rightNode = temp; return; } TreeNode* invertTree(TreeNode* root) { if (root == NULL) return invertTree(root->left) } }; Solution C++

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

Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

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

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1 Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2 Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Solution Time: O(logN)

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

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n). Example 1 Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2 Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Solution (binary search) Java

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

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

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

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

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