mediumStackPattern: Stack
Validate Packet Shadows Solution
Problem Statement
Given a sequence of packets where each packet contains an identifier and a corresponding shadow identifier, determine if the sequence is valid based on the condition that the shadow identifiers must be matched in reverse order.
Examples
Example 1:
Input:[[1, 2], [2, 3], [3, 1]]
Output:false
Explanation: The shadow identifiers [2, 3, 1] are matched in reverse order.
Example 2:
Input:[[1, 2], [2, 3], [3, 4]]
Output:false
Explanation: The shadow identifiers [2, 3, 4] are not matched in reverse order.
Example 3:
Input:[]
Output:true
Explanation: An empty sequence is considered valid.
Constraints
- 1 <= packet length <= 1000
- 1 <= identifier <= 1000
- 1 <= shadow identifier <= 1000
- All identifiers and shadow identifiers are unique.
Time: O(n) Space: O(n)
The optimized approach involves using a stack data structure to keep track of the shadow identifiers and iterating through the sequence only once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def validate_packet_shadows(packets):
stack = []
for packet in packets:
stack.append(packet[1])
for packet in reversed(packets):
if stack.pop() != packet[0]:
return False
return True