Happy New Year! Easy problem by LC

Hello Everyone, and Happy New Year to all of you, wishing you to stay safe and sound, and to have a kick-ass 2021 ahead. In other words, wishing that Happiness(2021) >> Happiness(2020).

The first problem of the year seems computationally challenging, if it wasn't for one phrase. Here it is: Largest Subarray Length K - LeetCode

1708. Largest Subarray Length K

Easy

An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].

For example, consider 0-indexing:

• [1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2.
• [1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2.

A subarray is a contiguous subsequence of the array.

Given an integer array nums of distinct integers, return the largest subarray of nums of length k.

 

Example 1:

Input: nums = [1,4,5,2,3], k = 3
Output: [5,2,3]
Explanation: The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3].
Of these, [5,2,3] is the largest.

Example 2:

Input: nums = [1,4,5,2,3], k = 4
Output: [4,5,2,3]
Explanation: The subarrays of size 4 are: [1,4,5,2], and [4,5,2,3].
Of these, [4,5,2,3] is the largest.

Example 3:

Input: nums = [1,4,5,2,3], k = 1
Output: [5]

 

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 109
• All the integers of nums are unique.

Indeed, because the numbers are all unique, you can avoid the K*Nums.Length complexity (which would be intractable since that would explode to 10^10) and rather perform an O(N) search. In fact, all you have to do is look for the largest number :) That will be the beginning of your sub-array. Solution works, and fast. Code is below, cheers, ACC.

public int[] LargestSubarray(int[] nums, int k)
{
    int maxVal = 0;
    int maxIndex = 0;

    for (int i = 0; i < nums.Length - k + 1; i++)
    {
        if (nums[i] > maxVal)
        {
            maxVal = nums[i];
            maxIndex = i;
        }
    }

    int[] retVal = new int[k];
    for (int i = 0; i < k; i++)
    {
        retVal[i] = nums[i + maxIndex];
    }

    return retVal;
}