# Posts published in “Easy”

Given a Binary Search Tree (BST) with the root nodeĀ root, returnĀ the minimum difference between the values of any two different nodes in the tree.

Example :

Note:

1. The size of the BST will be between 2 andĀ 100.
2. The BST is always valid, each node’s value is an integer, and each node’s value is different.

Solution 1: In order traversalĀ

Time complexity: O(n)

Space complexity: O(n)

C++

Related Problems:

A matrix isĀ ToeplitzĀ if every diagonal from top-left to bottom-right has the same element.

Now given anĀ M x NĀ matrix, returnĀ TrueĀ if and only if the matrix isĀ Toeplitz.
Example 1:

Example 2:

Note:

1. matrixĀ will be a 2D array of integers.
2. matrixĀ will have a number of rows and columns in rangeĀ [1, 20].
3. matrix[i][j]Ā will be integers in rangeĀ [0, 99].

Idea:

Check m[i][j] with m[i-1][j-1]

Solution: Brute Force

Time complexity: O(n*m)

Space complexity: O(1)

C++

Java

Python3

é¢ē®å¤§ęļ¼ę±ē»å®čå“åļ¼ę°ēäŗčæå¶å½¢å¼äø­1ēäøŖę°äøŗē“ ę°äøŖēę°å­ēäøŖę°ć

Given two integersĀ LĀ andĀ R, find the count of numbers in the rangeĀ [L, R]Ā (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number ofĀ 1s present when written in binary. For example,Ā 21Ā written in binary isĀ 10101Ā which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Example 2:

Note:

1. L, RĀ will be integersĀ L <= RĀ in the rangeĀ [1, 10^6].
2. R - LĀ will be at most 10000.

Solution 1: Brute Force

C++

Java

Python2

Python2

Problem:

ImplementĀ int sqrt(int x).

Compute and return the square root ofĀ x.

xĀ is guaranteed to be a non-negative integer.

Example 1:

Example 2:

Ā

# Solution 1: Brute force

Time complexity: sqrt(x)

# Solution 2: Binary search

Time complexity: O(logn)

# Solution 3: Newton’s method

## Python3

é¢ē®å¤§ęļ¼ē»ä½ äøäøŖå­ē¬¦äø²åäøäŗč¦å ē²ēåčÆļ¼čæåå ē²åēHTMLä»£ē ć

Problem:

Given a set of keywordsĀ wordsĀ and a stringĀ S, make all appearances of all keywords inĀ SĀ bold. Any letters betweenĀ <b>Ā andĀ </b>Ā tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given thatĀ words = ["ab", "bc"]Ā andĀ S = "aabcd", we should returnĀ "a<b>abc</b>d". Note that returningĀ "a<b>a<b>b</b>c</b>d"Ā would use more tags, so it is incorrect.

Note:

1. wordsĀ has length in rangeĀ [0, 50].
2. words[i]Ā has length in rangeĀ [1, 10].
3. SĀ has length in rangeĀ [0, 500].
4. All characters inĀ words[i]Ā andĀ SĀ are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.