Zig-Zag World of Algorithm and Data Structures

Sunday, February 25, 2024

[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)

Friday, February 23, 2024

[LeetCode] Maximum Average Subarray I

Problem: You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

n == nums.length
1 <= k <= n <= 10^5
-10^4 <= nums[i] <= 10^4

Approach: This is clearly a sliding window problem. We can take sum of first k elements say 'sum' and then we slide the window by one i.e. remove first element of window from sum and add new element of the slided window to sum and record the max sum so far so every step looks like:

sum = sum - nums[start] + nums[i]
start++
max_sum = MAX(sum, max_sum)

Implementation in C#:

public double FindMaxAverage(int[] nums, int k)

    {
        int length = nums?.Length ?? 0;
        if (length < k)
        {
            return 0;
        }
        long sum = 0;
        int i = 0, start = 0;
        for (; i < k; ++i)
        {
            sum += nums[i];
        }
        long maxSum = sum;
        for (i = k; i < length; ++i)
        {
            sum = sum - nums[start++] + nums[i];
            maxSum = sum > maxSum ? sum : maxSum; 
        }
        return (double)maxSum / k;
    }

Complexity: O(n)

Saturday, February 17, 2024

[LeetCode] Kids With the Greatest Number of Candies

Problem: There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.

Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.

Note that multiple kids can have the greatest number of candies.

Example:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Approach: A simple problem to solve. Get the maximum of the given candies first. Once we get it, we just need to compare candies[i] + extraCandies with max of candies. If it is equal to or more than max of candies then add true to result otherwise add false.

Implementation in C#:

    public IList<bool> KidsWithCandies(int[] candies, int extraCandies) 
    {
        List<bool> result = new List<bool>();
        int maxCandy = this.findMaxCandy(candies);
        for (int i = 0; i < candies.Length; ++i)
        {
            result.Add(candies[i] + extraCandies >= maxCandy);
        }
        return result;
    }

    private int findMaxCandy(int[] candies)
    {
        int maxCandy = candies[0];
        for (int i = 1; i < candies.Length; ++i)
        {
            if (maxCandy < candies[i])
            {
                maxCandy = candies[i];
            }
        }
        return maxCandy;
    }

Complexity: O(n)

[LeetCode] Greatest Common Divisor of Strings

Problem: For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Approach: A simple approach would be to check for every prefix of the smaller string and check if the prefix is such that

prefix + prefix + prefix + ... + prefix = str1

prefix + prefix + prefix + ... + prefix = str2

We can do some optimization like choosing a prefix such that the length of prefix is divisor of lengths of both str1 and str2 and may be more but whatever optimization we will do the complexity is going to be on higher side i.e. O(m^2 + n^2).

Let's try to see problem from different view, sometimes looking at the examples really help. If you see closely, you can find GCD of str1 and str2 can exist only if

str1 + str2 = str2 + str1

Why? Let's say GCD of both strings is gcd then:

str1 = gcd + gcd + gcd + ... m times

str2 = gcd + gcd + gcd + ... n times

str1 + str2 = gcd + gcd + gcd + ... (m + n) times

str2 + str1 = gcd + gcd + gcd + ... (n + m) times

so you see str1 + str2 is equal to str2 + str1.

Now that we know when GCD exist, what is GCD of both strings? Just look at the example closely and you will quickly find that GCD is the prefix of length of GCD(Length(str1), Length(str2).

That's all!

Implementation in C#:

Brute-force:

    public string GcdOfStrings(string str1, string str2) 
    {
        string gcd = string.Empty;
        int str1Len = str1.Length;
        int str2Len = str2.Length;
        int minStrLen = Math.Min(str1Len, str2Len); 
        int currLen = 1;
        if (!string.IsNullOrEmpty(str1) && !string.IsNullOrEmpty(str2))
        {
            while (currLen <= minStrLen)
            {
                if (str1Len % currLen == 0 && str2Len % currLen == 0)
                {
                    string prefix = str1.Substring(0, currLen);
                    if (str2.StartsWith(prefix))
                    {
                        if (this.isStrRepetitionOfPrefix(str1, prefix)
                            && this.isStrRepetitionOfPrefix(str2, prefix))
                        {
                            gcd = prefix;
                        }
                    }
                }
                ++currLen;
            } 
        }
        return gcd;
    }

    private bool isStrRepetitionOfPrefix(string str, string prefix)
    {
        int i = prefix.Length;
        while(i < str.Length)
        {
            if (str.Substring(i, prefix.Length) != prefix)
            {
                return false;
            }
            i += prefix.Length;
        }
        return true;
    }

Optimized:

    public string GcdOfStrings(string str1, string str2) 
    {
        if (str1 + str2 != str2 + str1)
        {
            return string.Empty;
        }
        int maxLength = str1.Length;
        int minLength = str2.Length;
        if (maxLength < minLength)
        {
            minLength = maxLength;
            maxLength = str2.Length;
        }
        int gcdLength = this.getGCD(maxLength, minLength);
        return str1.Substring(0, gcdLength);
    }

    private int getGCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

Complexity: Solution 1: O(m^2 + n^2)

Solution 2: O(m + n)

Friday, February 16, 2024

[LeetCode] Merge Strings Alternately

Problem: You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example:

Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

Approach: It's a simple problem to solve, you can look directly at the implementation to understand the approach.

Implementation in C#:

    public string MergeAlternately(string word1, string word2)
    {
        // Safety checks
        if (string.IsNullOrEmpty(word1) && string.IsNullOrEmpty(word2))
        {
            return word1;
        }
        if (string.IsNullOrEmpty(word1))
        {
            return word2;
        }
        if (string.IsNullOrEmpty(word2))
        {
            return word1;
        }

        int i = 0, j = 0;
        StringBuilder sb = new StringBuilder();
        while (i < word1.Length && j < word2.Length)
        {
            sb.Append(word1[i++]);
            sb.Append(word2[j++]);
        }

        if (i < word1.Length)
        {
            this.AppendAllChars(sb, i, word1);
        }
        if (j < word2.Length)
        {
            this.AppendAllChars(sb, j, word2);
        }

        return sb.ToString();
    }

    private void AppendAllChars(StringBuilder sb, int index, string word)
    {
        while (index < word.Length)
        {
            sb.Append(word[index++]);
        }
    } 

Complexity: O(n)

Home

Sunday, February 25, 2024

Friday, February 23, 2024

Saturday, February 17, 2024

Friday, February 16, 2024