Zig-Zag World of Algorithm and Data Structures

Tuesday, February 27, 2024

[LeetCode] Unique Number of Occurrences

Problem: Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Example:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Input: arr = [1,2]
Output: false

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

Approach: We can use sorting to solve this problem but it will take nlogn time. To solve it in less time we can use a Map and a Set. First in the Map we will store the frequency of each element in the array and then we will traverse the Map and see if there are any repeated values in it using the Set.

That's all!

Implementation in C#:

    public bool UniqueOccurrences(int[] arr)
    {
        int length = arr?.Length ?? 0;
        if (length <= 1)
        {
            return true;
        }
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in arr)
        {
            if (!freqMap.ContainsKey(num))
            {
                freqMap[num] = 0;
            }
            ++freqMap[num];
        }
        HashSet<int> freqSet = new HashSet<int>();
        foreach (int key in freqMap.Keys)
        {
            if (!freqSet.Add(freqMap[key]))
            {
                return false;
            }
        }
        return true;
    }

Complexity: O(n)

[LeetCode] Find the Difference of Two Arrays

Problem: Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Approach: We can use HashSets to solve this issue. Just look at the implementation to understand the solution as it is straight forward.

Implementation in C#:

    public IList<IList<int>> FindDifference(int[] nums1, int[] nums2)
    {
        HashSet<int> num1Set = new HashSet<int>(nums1);
        HashSet<int> num2Set = new HashSet<int>(nums2);
        List<int> numsToRemove = new List<int>();
        foreach (int num in num1Set)
        {
            if (num2Set.Contains(num))
            {
                numsToRemove.Add(num);
            }
        }
        foreach (int num in numsToRemove)
        {
            num1Set.Remove(num);
            num2Set.Remove(num);
        }
        return new List<IList<int>> { num1Set.ToList(), num2Set.ToList() };
    }

Complexity: O(n)

Sunday, February 25, 2024

[LeetCode] Find Pivot Index

Problem: Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Approach: The approach is simple. We will calculate total sum first. Once we have calculated it, we just need to see at every index 'i' if Sum(nums[0]...nums[i - 1]) is equal to total sum - nums[i] - Sum(nums[0]...nums[i - 1]). Why?

What is Sum(nums[0]...nums[i - 1])? It is the sum of all the elements to the left of the element at i.

What is total sum - nums[i] - Sum(nums[0]...nums[i - 1])? It is the sume of the all the elements to the right of the element at index i. How?

total_sum = Sum(nums[0]...nums[n - 1])
total_sum - nums[i] = Sum(nums[0]...nums[i -1]) + Sum(nums[i + 1]...nums[n - 1])
total_sum - nums[i] - Sum(nums[0]...nums[i - 1]) = Sum(nums[i + 1]...nums[n - 1])

We can clearly see Sum(nums[i + 1]...nums[n - 1]) is sum of all the elements to the right of the element at index 'i'.

That's all!

Implementation in C#:

    public int PivotIndex(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length == 0)
        {
            return -1;
        }
        int totalSum = this.SumOfArray(nums);
        int leftSum = 0; 
        for (int i = 0; i < length; ++i)
        {
            if (leftSum == totalSum - nums[i] - leftSum )
            {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }

    private int SumOfArray(int[] nums)
    {
        int sum = 0;
        for (int i = 0; i < nums.Length; ++i)
        {
            sum += nums[i];
        }
        return sum;
    }

Complexity: O(n)

[LeetCode] Find the Highest Altitude

Problem: There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Approach: The approach is simple; we just keep adding every gain in current altitude and comparing it with max altitude. Assign max altitude to current altitude if max is less than current altitude.

Implementation in C#:

    public int LargestAltitude(int[] gain)
    {
        int length = gain?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        int maxAlt = 0, currAlt = 0;
        for (int i = 0; i < length; ++i)
        {
            currAlt += gain[i];
            maxAlt = maxAlt < currAlt ? currAlt : maxAlt;
        }
        return maxAlt;
    }

Complexity: O(n)

[LeetCode] Longest Subarray of 1's After Deleting One Element

Problem: Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Approach: This problem is similar to problem of maximum number of consecutive 1's in the array if you can flip at most k 0's. Here is k is constant which is 1 so here too we are going to take sliding window approach and answer is the max window size - 1.

Implementation in C#:

    public int LongestSubarray(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        int start = 0, end = 0, k = 1;
        for (; end < length; ++end)
        {
            if (nums[end] == 0)
            {
                --k;
            }
            if (k < 0)
            {
                if (nums[start++] == 0)
                {
                    ++k;
                }
            }
        }
        return end - start - 1; 
    }

Complexity: O(n)

[LeetCode] Max Consecutive Ones III

Problem: Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Approach: This is kind of again a sliding window problem but here the window size is not constant. The window size can be expanded till the condition is satisfied which is the window must have at most k 0's.

We can expand the window till the above condition is satisfied i.e. we keep increasing the end but when we see the window has k + 1 0's, we start shrinking the window from the left i.e. we keep increasing start till we get nums[start] = 0. To reduce this iteration we can use queue to store the indices of all 0's so that we can directly jump to back of queue + 1 index to find the next start. At any point of time the current window size would be end - start.

If you see from the above approach we would be able to solve this problem in linear time but we are taking extra storage. Off course we can remove this extra storage but in that case we might end up doing 2 * n steps. Anything else we can do to improve it further?

Just think whenever current window can be expanded i.e. window has at most k 0's, start doesn't move and in the end the max distance is really end - start. Means in case of k + 1 0's we keep increasing the start and end is anyway alwasy increasing. So even if we don't reach the 0 to shrink the window the size of the remains same till the above condition is not satisfied because we keep incrementing start by 1 at every step.

That's all

Implementation in C#:

With Queue:

    public int LongestOnes(int[] nums, int k)
    {
        int length  = nums?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        Queue<int> zeroIndicesQ = new Queue<int>();
        int maxLength = 0, start = 0;
        bool isFirstZero = true;
        for (int i = 0; i < length; ++i)
        {
            if (nums[i] == 0)
            {
                zeroIndicesQ.Enqueue(i);
                --k;
                if (k < 0)
                {
                    k = 0;
                    maxLength = maxLength < i - start ?
                                i - start :
                                maxLength;
                    start = zeroIndicesQ.Dequeue() + 1;
                }
            }
        }
        return maxLength < length - start ?
               length - start :
               maxLength;
    }

Optimized way:

public int LongestOnes(int[] nums, int k)

    {
        int length  = nums?.Length ?? 0;
        if (length == 0)
        {
            return 0;
        }
        int start = 0, end = 0;
        for (; end < length; ++end)
        {
            if (nums[end] == 0)
            {
                --k;
            }
            if (k < 0)
            {
                if (nums[start] == 0)
                {
                    ++k;
                }
                ++start;
            }
        }
        return end - start;
    }

Complexity: O(n)

[LeetCode] Maximum Number of Vowels in a Substring of Given Length

Problem: Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Approach: We can take all the substring of size k of given string s and can check the number of vowels in those substrings and then we can return the maximum of all those counts but that will be time consuming task.

We can use sliding window approach here to solve this problem. Obviously the size of the window here will be k. First we take the first k characters of s and count the number of vowels in it. Now we slide this k sized window one by one. The vowel count of the sliding window will be modified as follows:

curr_vowel_count = curr_vowel_count - IsVowel(s[start]) + IsVowel(s[curr_index])

Here the curr_index is the end of the window and start is obviously the start of the window.

Implementation in C#:

public int MaxVowels(string s, int k)

    {
        int length = s?.Length ?? 0;
        if (length < k)
        {
            return 0;
        }
        int currVowelCount = 0, i = 0;
        for (; i < k; ++i)
        {
            if (this.IsVowel(s[i]))
            {
                ++currVowelCount;
            }
        }
        int start = 0, maxVowelCount = currVowelCount;
        for (; i < length; ++i)
        {
            if (this.IsVowel(s[start++]))
            {
                --currVowelCount;
            }
            if (this.IsVowel(s[i]))
            {
                ++currVowelCount;
                maxVowelCount = maxVowelCount < currVowelCount ? 
                                currVowelCount : 
                                maxVowelCount;
            }
        }
        return maxVowelCount;
    }

    private bool IsVowel(char ch)
    {
        return ch == 'a' ||
               ch == 'e' ||
               ch == 'i' ||
               ch == 'o' ||
               ch == 'u'; 
    }

Complexity: O(n)

Home

Tuesday, February 27, 2024

Sunday, February 25, 2024