What is the time complexity of my isSubsequent (LeetCode)?

Question

I am working on the follow up question to isSubsequence from leetcode and need to know what the time complexity for my solution is. I am just starting to figure big-O out and would love some help on figuring out what it is for this one and how I can begin to understand why it is what it is. I believe this is O(n log n) but couldn't explain why other than the fact that I use a binary search

    const s = 'a';
const t = 'abc';

function populateHashTable(t) {
  const letterToIndexHashTable = {}; // {a: [0], b: [1], c: [2]}

  for (let i = 0; i < t.length; i++) {
    const currentLetter = t[i]; 
    if (currentLetter in letterToIndexHashTable) {
      letterToIndexHashTable[currentLetter].push(i);
    } else {
      letterToIndexHashTable[currentLetter] = [i];
    }
  }

  return letterToIndexHashTable;
}

const letterToIndexHashTable = populateHashTable(t); // {a: [0], b: [1], c: [2]}


function isSubsequence(s) {
  let previousIndex = 0;
  let lettersMatched = 0;

  for (let i = 0; i < s.length; i++) {
    const currentLetter = s[i];
    if (currentLetter in letterToIndexHashTable) {
      const nextLetterInSubsequence = letterToIndexHashTable[currentLetter]
        .find(element => element >= previousIndex);
      if (nextLetterInSubsequence >= 0) {
        previousIndex = nextLetterInSubsequence;
        lettersMatched++;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
  if (lettersMatched === s.length) {
    return true;
  } else {
    return false;
  }
}

Emma Marcier · Accepted Answer · 2020-10-23 22:21:22Z

0

Not sure what happened to my previous edit. Here is my breakdown:


function populateHashTable(t) {
    // Here we would have an O(N) space
    const letterToIndexHashTable = {}; // {a: [0], b: [1], c: [2]}

    for (let i = 0; i < t.length; i++) { // This for loop would be O(N)
        const currentLetter = t[i];
        if (currentLetter in letterToIndexHashTable) { // This would be O(1)
            letterToIndexHashTable[currentLetter].push(i);  // This would be O(1)
        } else {
            letterToIndexHashTable[currentLetter] = [i];  // This would be O(1)
        }
    }

    return letterToIndexHashTable;
}

const letterToIndexHashTable = populateHashTable(t);  // This would be O(N) time and O(N) space


function isSubsequence(s) {
    let previousIndex = 0;
    let lettersMatched = 0;

    for (let i = 0; i < s.length; i++) { // This for loop would be O(N)
        const currentLetter = s[i];
        if (currentLetter in letterToIndexHashTable) {  //  This would be O(N)
            const nextLetterInSubsequence = letterToIndexHashTable[currentLetter]
                .find(element => element >= previousIndex); // One might argue this would be O(N), but I'm not sure.
            if (nextLetterInSubsequence >= 0) {
                previousIndex = nextLetterInSubsequence;
                lettersMatched++;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    if (lettersMatched === s.length) {
        return true;
    } else {
        return false;
    }
}

My guess is that your solution might be O(N ^ 3) runtime and O(N) space, I might be wrong though (not a big-o expert):
We can use two pointers for solving this problem:

const isSubsequence = function(s, t) {
    
    let left = 0;
    let right = 0;
    
    while (right < t.length) {
        if (s[left] === t[right]) {
            ++left;
        }

        ++right;
    }

    if (left === s.length) {
        return true;
    }

    return false;
};

Reference

What is the time complexity of Javascript Array.reduce() and Array.find()?

edited Oct 23, 2020 at 22:21

answered Oct 23, 2020 at 21:31

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jake Mulhern Over a year ago

so this is actually the follow up to the basic question that asks what you would do if you had a bunch of s strings instead of just one which is why I wrote it out this way. My original answer to the more basic question was O(n) for sure. Is this also O(n)?

Jake Mulhern Over a year ago

Thanks for taking the time to even look at it!

Collectives™ on Stack Overflow

What is the time complexity of my isSubsequent (LeetCode)?

1 Answer 1

Reference

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Reference

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related