An NLogN Non-Sorting Solution II

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  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 11, the decimal representation is "11". The substring s[10..11] is "11", which matches, so index 11 is good.

• At index 12, the decimal representation is "12". The substring s[11..12] is "12", which matches, so index 12 is good.

No other index has a substring ending at it that equals its decimal representation. Therefore, the answer is [0, 11, 12].

Example 2:

Input: s = "01234"

Output: [0,1,2,3,4]

Explanation:

For every index i from 0 to 4, the decimal representation of i is a single digit, and the substring s[i] matches that digit.

Therefore, a valid substring ending at each index exists, making all indices good.

Example 3:

Input: s = "12345"

Output: []

Explanation:

No index has a substring ending at it that matches its decimal representation.

Therefore, there are no good indices and the result is an empty array.

 

Constraints:

• 1 <= s.length <= 105
• s only consists of digits from '0' to '9'.

public class Solution {
    public IList GoodIndices(string s)
    {
        List retVal = new List();

        for(int i = 0; i < s.Length; i++)
        {
            int len = i.ToString().Length;

            int currentNumber = 0;
            bool potentialCandidate = true; ;
            for (int j = 0; j < len; j++)
            {
                int index = i - len + j + 1;
                if (index < 0)
                {
                    potentialCandidate = false;
                    break;
                }
                currentNumber = 10 * currentNumber + (int)(s[index] - '0');
                if(currentNumber > i)
                {
                    potentialCandidate = false;
                    break;
                }
            }
            if (potentialCandidate && currentNumber == i)
            {
                retVal.Add(i);
            }
        }

        return retVal;
    }
}