Subtract the Next Smaller Value
Updated
Problem statement
You are given an integer array nums. For each index i, look to the right of i and find the first value that is smaller than nums[i]: the value nums[j] with the smallest index j > i such that nums[j] < nums[i].
The new value at index i is nums[i] - nums[j]. If no value to the right of i is smaller, the value at index i stays the same. A value equal to nums[i] is not smaller, so it is skipped.
Every index uses the original values of nums. Return the array of new values.
Function
subtractNextSmaller(nums: int[]) → int[]Examples
Example 1
nums = [7,9,5,9,6]return = [2,4,5,3,6]For 7 and the first 9, the first smaller value to the right is 5, so they become 2 and 4. Nothing after 5 is smaller than 5, so it stays 5. The second 9 meets 6 next, so it becomes 3, and the last value, 6, has nothing after it.
Example 2
nums = [4,4,10,1,4]return = [3,3,9,1,4]The second 4 is equal to the first 4, not smaller, so the first 4 keeps looking and stops at 1. Both 4s and the 10 subtract 1. The 1 has no smaller value after it, and the last 4 has nothing after it, so both stay.
Example 3
nums = [1000000000,999999999,1000000000]return = [1,999999999,1000000000]The first value subtracts 999999999 and becomes 1. The value 999999999 has only a larger value after it, so it stays, and the last value stays too.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^9
More Expedia Phone Screen questions
- Find the Shortest Round TripPHONE SCREEN · Seen Jul 2026
- Two SumPHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2024
- Merge Two Sorted Linked ListsPHONE SCREEN · ONSITE INTERVIEW · Seen May 2023
- Assign CookiesPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2022
- Kth Smallest Value in a BSTPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2022
- Reverse a Singly Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2022
- Climbing StairsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2021
- First Substring OccurrencePHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2021
- Array Containment with MultiplicitiesPHONE SCREEN · Seen Nov 2019
- Merge Sorted Arrays in PlacePHONE SCREEN · ONSITE INTERVIEW · Seen May 2019
Similar questions at other companies
- Next Taller Building to the RightTemu · PHONE SCREENTemu interview questions
- Minimum StackSnowflake · PHONE SCREENSnowflake interview questions
- Constant-Time Minimum StackLinkedIn · PHONE SCREENLinkedIn interview questions
- Trapping Rain WaterBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Asteroid CollisionSiemens · PHONE SCREEN
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Daily TemperaturesCARS24 · PHONE SCREEN
- Next Greater Indices and Maximum GapTikTok · PHONE SCREENTikTok interview questions
- Count Visible People to the LeftGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)