educative.io

Why do we need to check for greather than zero? + sc question

Courses
,
#1

Hello! can someone explain why we need the ‘|| 0’ in the. below line?

if (wordsSeen[word] > (wordFrequency[word] || 0)) {
break;
}

I’ve tried to work through different examples but can’t really justify having it there. Isn’t wordsSeen[word] always greater than zero?

Also for the space complexity -

The space complexity of the algorithm is O(M) since at most, we will be storing all the words in the two HashMaps. In the worst case, we also need O(N) space for the resulting list. So, the overall space complexity of the algorithm will be O(M+N).

so is it O(M+N) or O(M)? I’m confused whether they are the same or different

Thanks in advance!!

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 4 - Grokking the Coding Interview: Patterns for Coding Questions

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 4 - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @Jennifer_Herrarte , Thank you for contacting the Educative team with your query!

For your first question: If the word does not exist in the wordFrequency HashMap, the code will return an error. To avoid that error, there is an additional || 0 given, meaning if the word does not exist in the HashMap, the code will still proceed without giving an error.

For your second question: O(M) is the space required for storing all the words in the two HashMaps and O(N) is the space for the resulting list. So, the overall space complexity of the algorithm will be O(M+N). However, for this particular case, the upperbound for N is very small so we can consider the space complexity to be O(M).

Please feel free to reply here if there is still some confusion.

Hope you have an amazing learning experience on Educative!

1 Like
#3 
  if (!(word in wordFrequency)) { // Break if we don't need this word
    break;
  }

Wouldn’t the line above mitigate that possibility?

1 Like