Sort Colors
Function Name: sortColors
Description
Given an array consisting of n objects with '0's, '1's, and '2's, sort the array in-place so that objects of the same color are adjacent, with the colors in the order of '0', '1', and '2'.
You are not allowed to use the library's sort function and should solve this problem with a linear complexity O(n).
The function should modify the array in-place and does not need to return anything.
Requirements
- The function should take a single parameter: an array of integers which will only contain the values 0, 1, or 2.
- The sorting must be done in-place with no use of extra space, except for constant space complexity such as extra variables.
- Optimize the function for the best time complexity possible, ideally linear time O(n).
- Helper functions are permitted as long as they adhere to the same space complexity constraints.
Examples
If the input array is [2, 0, 2, 1, 1, 0], then after calling sortColors(arr), the array should be modified to [0, 0, 1, 1, 2, 2].Calling sortColors([2, 0, 1]) should change the array to [0, 1, 2].Calling sortColors([0, 0, 0]) should leave the array unchanged.
Links
Find Peak Element
Thu Nov 14 2024
Given an array of integers nums, write a function 'findPeakElement' that returns the index of any peak element. A peak element is an element that is greater than its neighbors. For the purposes of this problem, consider that the 'nums' array has -Infinity as neighbors past its bounds, meaning that if the first or last element is greater than their single neighbor (inside the array), they could be considered peak elements as well.You must write an algorithm that runs in O(log n) time complexity.
Duplicate Number Finder
Sat Nov 16 2024
Write a function 'findDuplicate' that takes an array of integers. The array contains integers in the range 1 to n (inclusive), with one integer appearing exactly twice. Your task is to find and return the duplicate integer.