easyStackPattern: Stack
Validate Message Timestamps Solution
Problem Statement
Given an array of integers representing message timestamps, determine if the received messages can be sent in the original order. You are given an array of timestamps where each timestamp represents the time a message was received.
Examples
Example 1:
Input:[1, 2, 3, 4, 5]
Output:true
Explanation: The messages can be sent in the original order
Example 2:
Input:[5, 4, 3, 2, 1]
Output:false
Explanation: The messages cannot be sent in the original order
Example 3:
Input:[1, 3, 2, 4, 5]
Output:false
Explanation: The messages cannot be sent in the original order
Constraints
- 1 <= timestamps.length <= 100000
- -100000 <= timestamps[i] <= 100000
Time: O(n) Space: O(n)
Optimized approach uses a stack data structure to keep track of the valid order of timestamps, achieving a time complexity of O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def validate_message_timestamps(timestamps):
for i in range(1, len(timestamps)):
if timestamps[i] < timestamps[i - 1]:
return False
return True