Binary Search to Find Next Greater Element

This was a problem that required me to literally sleep over it to come up with a solution. The way I was solving it had a time complexity of O(N*M*S) where N=50K, M=50 and S=10K, which becomes intractable. The way to speed it up then was to perform a binary search to find the next greater element given a certain number (in the case of the problem an index). Complexity reduced to O(N*M*Log(S)), which was doable. Code is down below, take a look, cheers, ACC.

Number of Matching Subsequences - LeetCode

792. Number of Matching Subsequences

Medium

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

 

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

public int NumMatchingSubseq(string s, string[] words)
{
    List[] list = new List[26];
    for (int i = 0; i < list.Length; i++) list[i] = new List();

    //O(n)
    for (int i = 0; i < s.Length; i++)
    {
        int index = (int)(s[i] - 'a');
        list[index].Add(i);
    }

    //O(|words| * |word| * Log(|s|)) = 5000*50*5 = 1.3M
    int retVal = 0;
    foreach (string word in words)
    {
        int minIndex = -1;
        foreach (char c in word)
        {
            int index = (int)(c - 'a');
            minIndex = FindMinIndexGreaterThanNumber(list[index], minIndex);
            if (minIndex == -1)
            {
                break;
            }
        }
        retVal = (minIndex != -1) ? retVal + 1 : retVal;
    }

    return retVal;
}


public int FindMinIndexGreaterThanNumber(List list, int number)
{
    if (list.Count == 0 || number >= list.Last()) return -1;

    int left = 0;
    int right = list.Count - 1;

    while (left < right)
    {
        int middle = (left + right) / 2;

        if (list[middle] == number)
        {
            if (middle + 1 < list.Count) return list[middle + 1];
            else return -1;
        }
        else if (list[middle] < number)
        {
            left = middle + 1;
        }
        else
        {
            right = middle;
        }
    }

    if (list[left] > number) return list[left];
    else if (left + 1 < list.Count && list[left + 1] > number) return list[left + 1];
    return -1;
}