Problem There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned. Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity. ...
Problem Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Implement the Solution class: Solution(int[] nums) Initializes the object with the array nums. int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i’s, then each index should have an equal probability of returning. Examples Example 1: ...
Problem Given an integer num, repeatedly add all its digits until the result has only one digit, and return it. Examples Example 1: Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it. ...
Binary Tree Cameras Problem Problem You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree. Examples Example 1: ...
Problem The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation. For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer num, return its complement. Examples Example 1: Input: num = 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. ...
Problem Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example Example 1: $$ \begin{bmatrix} \color{red} A & \color{red} B & \color{red} C & E \\ S & F & \color{red} C & S \\ A & \color{red} D & \color{red} E & E \end{bmatrix} $$ ...
Problem Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word. Examples Example 1: ...
Problem Given a string, find the length of the longest substring without repeating characters. Examples Example 1: Input: s = "aababcbb" Output: 3 Explanation: The longest substring without repeating characters is "abc". Example 2: Input: s = "cccc" Output: 1 Explanation: The longest substring without repeating characters is "c". ...
Problem Given a document (or stream) of words. Find the top k most frequent words in the document (or stream). OR Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order. Examples Example 1: Input: words = ["i","love","leetcode","i","love","coding"], k = 2 Output: ["i","love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order. ...
This is a follow up on H-Index Problem. What if the citations array is sorted in ascending order? Could you optimize your algorithm? Problem Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in an ascending order, return compute the researcher’s h-index. According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each. ...