Teemo Attacking – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration
seconds. More formally, an attack at second t
will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1]
. If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration
seconds after the new attack.
You are given a non-decreasing integer array timeSeries
, where timeSeries[i]
denotes that Teemo attacks Ashe at second timeSeries[i]
, and an integer duration
.
Return the total number of seconds that Ashe is poisoned.
Example 1:
Input: timeSeries = [1,4], duration = 2 Output: 4 Explanation: Teemo's attacks on Ashe go as follows: - At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2. - At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5. Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.
Example 2:
Input: timeSeries = [1,2], duration = 2 Output: 3 Explanation: Teemo's attacks on Ashe go as follows: - At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2. - At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3. Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.
Constraints:
1 <= timeSeries.length <= 104
0 <= timeSeries[i], duration <= 107
timeSeries
is sorted in non-decreasing order.
C++ Teemo Attacking LeetCode Solution
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int len = timeSeries.size();
if (!len) return 0;
int result = duration;
for (int i = 1; i < len; i++) {
result += min(duration, timeSeries[i] - timeSeries[i - 1]);
}
return result;
}
};
Java Teemo Attacking LeetCode Solution
public class Solution {
public int findPosisonedDuration(int[] timeSeries, int duration) {
if (timeSeries == null || timeSeries.length == 0 || duration == 0) return 0;
int result = 0, start = timeSeries[0], end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.length; i++) {
if (timeSeries[i] > end) {
result += end - start;
start = timeSeries[i];
}
end = timeSeries[i] + duration;
}
result += end - start;
return result;
}
}
Python 3 Teemo Attacking LeetCode Solution
class Solution(object):
def findPoisonedDuration(self, timeSeries, duration):
ans = duration * len(timeSeries)
for i in range(1,len(timeSeries)):
ans -= max(0, duration - (timeSeries[i] - timeSeries[i-1]))
return ans
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1