[LeetCode] Kth Smallest Number in Multiplication Table

668. Kth Smallest Number in Multiplication Table

Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).

Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.

Read more
[LeetCode] All O'one Data Structure

432. All O`one Data Structure

Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

  • AllOne() Initializes the object of the data structure.
  • inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
  • dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
  • getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string “”.
  • getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string “”.
Read more
[LeetCode] Subarrays with K Different Integers

992. Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

  • For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

Read more
[LeetCode] Concatenated Words

472. Concatenated Words

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Read more
[LeetCode] Arithmetic Slices II - Subsequence

446. Arithmetic Slices II - Subsequence

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
  • For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

  • For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

Read more
[LeetCode] Score of Parentheses

856. Score of Parentheses

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

  • “()” has score 1.
  • AB has score A + B, where A and B are balanced parentheses strings.
  • (A) has score 2 * A, where A is a balanced parentheses string.
Read more
[LeetCode] Shortest Path to Get All Keys

864. Shortest Path to Get All Keys

You are given an m x n grid grid where:

  • ‘.’ is an empty cell.
  • ‘#’ is a wall.
  • ‘@’ is the starting point.
  • Lowercase letters represent keys.
  • Uppercase letters represent locks.

You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.

If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

Read more
[LeetCode] Number of Distinct Islands

694. Number of Distinct Islands

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Return the number of distinct islands.

Read more
[LeetCode] Minimum Moves to Move a Box to Their Target Location

1263. Minimum Moves to Move a Box to Their Target Location

A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.

The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box.

Your task is to move the box ‘B’ to the target position ‘T’ under the following rules:

  • The character ‘S’ represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).
  • The character ‘.’ represents the floor which means a free cell to walk.
  • The character ‘#’ represents the wall which means an obstacle (impossible to walk there).
  • There is only one box ‘B’ and one target cell ‘T’ in the grid.
  • The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
  • The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Read more
[LeetCode] Minimum Cost Tree From Leaf Values

1130. Minimum Cost Tree From Leaf Values

Given an array arr of positive integers, consider all binary trees such that:

  • Each node has either 0 or 2 children;
  • The values of arr correspond to the values of each leaf in an in-order traversal of the tree.
  • The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
    Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

A node is a leaf if and only if it has zero children.

Read more