Solve PTO window and sparse unique counting
Overview
This question evaluates proficiency in array algorithms and algorithmic optimization, including reasoning about contiguous subarray manipulation, efficient counting in sorted sequences, complexity analysis, and robust edge-case handling.
Design algorithms for two problems:
A) Longest vacation with limited PTO: Given an array A of characters where 'w' denotes a workday and 'h' denotes a holiday, and an integer n representing the number of PTO days you may spend to convert 'w' into a day off, return the maximum length of a contiguous vacation (consecutive days off) you can achieve. Example: A = ['w','h','h','w','h','w'], n = 2 => result = 5. State the function signature, outline an O(n) approach, analyze time and space complexity, and cover edge cases (all 'w', all 'h', n ≥ number of 'w', empty input).
B) Count uniques in a mostly-duplicate sorted array: Given a non-decreasing array where the number of distinct values is very small relative to its length, count the number of unique values faster than O(n). Propose an algorithm that exploits the sorted structure (e.g., divide-and-conquer or binary search to skip duplicate runs), provide complexity analysis, and discuss when it outperforms a linear scan.