3-liner very short C++ O(N) time O(1) space, only count increments (with explanation)


  • 0

    This is actually a very easy problem covered by a gaming story.

    Key Observation: The extra poison duration caused by an attack at time point t[i] is either the full duration or time increment t[i]-t[i-1], whichever is smaller.

    So the algorithm will become very straightforward.

        int findPoisonedDuration(vector<int>& t, int duration) {
          int res = t.empty()? 0 : duration;
          for (int i = 1; i < t.size(); ++i) res += min(t[i]-t[i-1], duration);
          return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.