Another Casual Coder

Here is another problem whose solution runs in O(nlogn) time but there is no sorting involved. Basically each index i represents a number N. All you need to do is check if the Len(N) previous indexes form the number N. But Len(N) in this case would be Log(N). Since you do that for every index, you end up with NLogN time complexity. Code is down below, cheers, ACC. Good Indices in a Digit String - LeetCode You are given a string  s  consisting of digits. An index  i  is called  good  if there exists a  substring  of  s  that ends at index  i  and is equal to the decimal representation of  i . Return an integer array of all good indices in  increasing order .   Example 1: Input:   s = "0234567890112" Output:   [0,11,12] Explanation:​​​​​​​ At index 0, the decimal representation of the index is  "0" . The substring  s[0]  is  "0" , which matches, so index  0  is good. At index...

Backtracking is a powerful strategy, and yes if can become exponential even with pruning, but remember that exponential might still be acceptable depending on the size of the input. For instance, in this case there isn't a lot of pruning and the solution ends up being N^4, but N = 15 in this case which is about 50K iterations which is for all practical purposes a "linear" solution. Code is down below, cheers, ACC. Word Squares II - LeetCode You are given a string array  words , consisting of  distinct  4-letter strings, each containing lowercase English letters. A  word square  consists of 4  distinct  words:  top ,  left ,  right  and  bottom , arranged as follows: top  forms the  top row . bottom  forms the  bottom row . left  forms the  left column  (top to bottom). right  forms the  right column  (top to bottom). It must satisfy: top[0] == left[0] ,  top[3] == right[0] ...