Solve various LeetCode data-structure questions
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 129. Sum Root to Leaf Numbers LeetCode 2089. Find Target Indices After Sorting Array LeetCode 270. Closest Binary Search Tree Value LeetCode 1249. Minimum Remove to Make Valid Parentheses LeetCode 303. Range Sum Query – Immutable LeetCode 746. Min Cost Climbing Stairs
https://leetcode.com/problems/sum-root-to-leaf-numbers/description/ https://leetcode.com/problems/find-target-indices-after-sorting-array/description/ https://leetcode.com/problems/closest-binary-search-tree-value/description/ https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/ https://leetcode.com/problems/range-sum-query-immutable/description/ https://leetcode.com/problems/min-cost-climbing-stairs/description/
Quick Answer: This collection evaluates proficiency in fundamental data structures and algorithms — including tree traversal and binary search tree reasoning, array manipulation and counting, string/stack validation for parentheses, prefix-sum range queries, and basic dynamic programming — within the Coding & Algorithms domain.
Given an integer array nums and an integer target, sort nums in non-decreasing order and return a list of all indices where target appears in the sorted array. Indices are 0-based and must be returned in increasing order.
Constraints
- 1 <= len(nums) <= 100000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Return indices in increasing order
Solution
def target_indices(nums: list[int], target: int) -> list[int]:
# Count elements less than target and equal to target
less = 0
equal = 0
for x in nums:
if x < target:
less += 1
elif x == target:
equal += 1
# The target will occupy indices [less, less + equal - 1] after sorting
if equal == 0:
return []
return list(range(less, less + equal))
Explanation
Instead of sorting, count how many elements are less than target (less) and how many are equal to target (equal). In the sorted array, all elements less than target come first, so target will start at index 'less' and occupy 'equal' consecutive positions. Construct and return that index range. If the target does not appear, return an empty list.
Time complexity: O(n). Space complexity: O(1) auxiliary (excluding output).
Hints
- Sorting nums and scanning for target works in O(n log n).
- You can avoid sorting: count how many elements are less than target and how many equal target.
- If cLess is the count of elements < target and cEq is the count == target, the answer is the range [cLess, cLess + cEq - 1].