DEV Community: Subhradeep Saha

Solving a Leetcode problem daily — Day 12 | 347. Top K frequent elements

Subhradeep Saha — Sun, 19 May 2024 04:21:39 +0000

Solving a Leetcode problem daily — Day 12 | 347. Top K frequent elements | by Subhradeep Saha | May, 2024 | Dev Genius

A detailed blog on how to use min heap for solving Leetcode’s 347 Top K frequent elements problem.

blog.devgenius.io

Here is the Leetcode problem link — 347. Top K frequent elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

High Level Approach

The goal is to determine the frequency of each element in the input array and return the top k elements with the highest frequencies.

First, we store the frequency of each element in a map. Next, we use a min-heap to store the {frequency, element} pairs from the map. We then iterate over each entry in the map:

If the heap size is less than k, we create a {frequency, element} pair and push it to the heap.
If the heap size is ≥ k, and the frequency of the element at the top of the heap is less than the current element’s frequency, we remove the lower frequency element and insert the higher frequency element into the heap.

The top of the min-heap will always contain the element with the lowest frequency among those in the heap, making it safe to remove when a higher frequency element is encountered. This ensures that, in the end, the heap contains the top k elements with the highest frequencies, which can then be returned as the answer.

Code Implementation in C++

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for(int& x: nums) {
            count[x]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, 
greater<pair<int, int>> > pq;

        for(auto& it: count) {
            if(pq.size() < k) {
                pq.push({it.second, it.first});
            }
            else {
                if(pq.top().first < it.second) {
                    pq.pop();
                    pq.push({it.second, it.first});
                }
            }
        }

        vector<int> ans;

        while(!pq.empty()) {
            ans.push_back(pq.top().second);
            pq.pop();
        }

        return ans;
    }
};

Detailed Code Breakdown:

Frequency Counting:

We create an unordered_map named count. This map will store each element in the array nums as the key and its frequency (the number of times it appears) as the value.
We iterate through the nums array using a range-based for loop, incrementing the corresponding element's count in the count map.

Priority Queue with Custom Comparison:

We declare a priority_queue named pq. This queue will hold pairs of (frequency, element) values.
The greater<pair<int, int>> comparison function ensures the priority queue prioritizes elements with lower frequencies which is being stored as the first element of the pair (lower frequency value will be at the top of the queue).

Populating the Priority Queue:

We iterate through the count map using a range-based for loop.
If the pq size is less than k (we haven't reached the desired number of elements yet), we directly add the (frequency, element) pair to the queue.
If the pq is already full and the current element's frequency is higher than the lowest frequency element in the queue:

=> We remove the element with the lowest frequency using pq.pop().

=> We add the current element with its higher frequency to the queue using pq.push().

Extracting Frequent Elements:

We create a vector named ans to store the final result (the k most frequent elements).
We iterate through the pq while it's not empty. For each iteration:

=> We extract the element (the second value in the pair) from the priority queue using pq.top().second and add it to the ans vector.

=> We remove the top from the queue using pq.pop().

Returning the Result:

The function returns the ans vector, which contains the k most frequent elements in the array.

Code Dry Run with Test Case:

Let’s consider the test case nums = [1,1,1,2,2,3], k = 2:

Frequency Counting:

The counter map is built as: count = {1: 3, 2: 2, 3: 1}

Priority Queue Population:

Iteration 1: Adding (3, 1)

Element: 1 (frequency: 3)
Since the heap is initially empty (pq.size() = 0 < k is true where k = 2), we directly add the (frequency, element) pair, which is (3, 1), to the priority queue.

Iteration 2: Adding (2, 2)

Element: 2 (frequency: 2)
The queue now has one element, and we need to consider two elements (pq.size() < k is still true).
The new element (2) has a frequency of 2, which is higher than the current lowest frequency (3) in the queue. This means element 2 appears less frequently than element 1.
Since the priority queue prioritizes lower frequencies, the new element (2, 2) is added directly to the heap.
Heap State: The heap now becomes [(2, 2), (3, 1)]. The element (2, 2) remains at the root because it has the lowest frequency(2)

Iteration 3: Adding (1, 3)

Element: 3 (frequency: 1)
The queue now has two elements, and k is still 2.
The new element (3) has a frequency of 1, which is not greater than the frequency(2) of the heap’s top element(2).
So we don't modify the queue and continue, ending the iteration over the counter map.
Heap State: The heap remains unchanged: [(2, 2), (3, 1)]. The element (3, 1) stays at the root as it maintains the lowest frequency.

Extracting Frequent Elements:

Heap state: [(2, 2), (3, 1)] — so we first push 2 to the ans vector
pop (2, 2) from the heap

3. get the heap’s top element which is 1 and push it to the ans vector.

4. pop the top element from the heap

5. since the heap is empty now:

the while loop is terminated and ans = {2, 1} is returned as the final output.

Note: the order of elements in the output doesn’t matter as mentioned in the problem.

Time and Space Complexity Analysis

The time and space complexity of the provided solution for finding the k most frequent elements can be analyzed as follows:

Time Complexity:

O(n log k): This is the dominant factor in the overall time complexity.

Iterating through the array: We iterate through the input array nums using a for loop. In the worst case, this loop iterates n times (where n is the number of elements in the array).

Priority Queue Operations:

Adding elements to the priority queue (pq.push()): The time complexity of adding an element to a min-heap is typically logarithmic, around O(log k) in most implementations. In our case, we potentially add elements up to k times (depending on the number of unique elements and their frequencies).
Removing elements from the priority queue (pq.pop()): Similar to adding, removing an element from a min-heap is also O(log k). We might perform this operation up to k times during the population stage.
Since the priority queue operations (push and pop) involve logarithmic time complexity and are potentially repeated up to k times, the overall time complexity is dominated by O(n log k).

Space Complexity:

O(n): This is primarily due to the usage of the hash map count.

The hash map count stores each element in the array as the key and its frequency as the value. In the worst case, the hash map can potentially store all unique elements from the input array, leading to a space complexity of O(n).
The priority queue pq itself stores a maximum of k elements (the k most frequent elements). While this contributes to space usage, it's typically considered negligible compared to the potentially larger count hash map, especially when k is a relatively small value compared to n.

Real-World Applications

Customer Analysis and Recommendation Systems: Online retail stores analyze customer purchase history to identify frequently bought items together. This information helps recommend complementary products, personalize promotions, and optimize product placement for better sales (e.g., suggesting frequently purchased groceries alongside main dishes).
Social Media and Trending Topics: Social media platforms like Twitter utilize algorithms to identify trending topics and hashtags in real-time. By analyzing the frequency of mentions and retweets, they can surface trending conversations and keep users engaged with the latest discussions.
Network Security and Intrusion Detection Systems (IDS): Network security systems monitor network traffic for suspicious activity. Identifying frequently occurring IP addresses attempting to access unauthorized resources or ports can be a red flag for potential attacks. By finding these frequent occurrences, security systems can trigger alerts and take preventive measures.

Conclusion

By employing a hash map for frequency counting and a priority queue with a custom comparison function, we efficiently identified the k most frequent elements in an array. This approach highlights the power of data structures for solving common data analysis problems in C++.

References

Cover photo by Waldemar on Unsplash
https://www.ibm.com/docs/SSNN4U_1.0.0/c_fan_rpt_customer_behavior_db.html
https://www.technologyreview.com/author/mit-technology-review-insights/
https://www.fortinet.com/resources/cyberglossary/intrusion-detection-system
Diagrams are made using Canva

Thank you for reading throughout! If you found this post insightful, please show your appreciation by liking this post and sharing it. Don’t forget to follow me for more engaging content like this. Your feedback is valuable, so please feel free to comment or reach out to me with any thoughts or suggestions.

Solving a Leetcode problem daily — Day 11 | Find Minimum in Rotated Sorted Array

Subhradeep Saha — Wed, 15 May 2024 03:50:13 +0000

Solving a Leetcode problem daily — Day 11 | Find Minimum in Rotated Sorted Array | by Subhradeep Saha | May, 2024 | Dev Genius

A detailed guide on how to solve Leetcode’s 153. Find minimum element in rotated sorted array problem using binary search.

blog.devgenius.io

Here is the Leetcode problem —153. Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n)time.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

Examples:

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

High-Level Approach

A direct method involves inspecting each element in the array to identify the minimum, but this would incur a time complexity of O(n). However, given that the input array exhibits a sorted-then-rotated characteristic, a more efficient approach could leverage binary search.

How are we getting the min element?

If somehow we get the index of the max element in the array, then the immediate next element will be the smallest item of the array.
If the maximum element is at the end of the array, the while loop won’t check the middle element from within. Hence, we return -1 in this case, signifying that the minimum element is at index -1+1 = 0, which is the first element.

Now how to identity the max element?

The rotation creates two distinct sorted halves, one with elements increasing from the start and another with elements decreasing towards the end.
The max value will be the one which is greater than its next number. So we divide the search space into half and check if the middle element is the max or not.

if its greater than its next number then we return it as the max element

To further optimize the search space in the next iteration, we can employ a strategy based on the comparison between the middle element and the array’s first element:

=> if the middle element is greater than the first element, it implies that the maximum value cannot exist in the left half of the array. Therefore, we can update the lower index to be m + 1.

=> conversely, if the middle element is less than the first element, it indicates that the maximum item lies in the lower half. Consequently, we can discard the right half and update the upper index to be m.

How are we updating the l, h and why?

In the while loop with the condition l < h, we’re ensuring that there are at least two items between l and h. Given that the middle index, m moves closer to the value of l when we divide by 2, we can confidently include the condition nums[m] > nums[m+1] without concerns about m+1 going beyond the array boundary. This adjustment streamlines the logic and simplifies the implementation.
Why do we update l to m+1 and not another value? It’s because when nums[m] > nums[m+1], it indicates that the maximum value is likely between indices l and m including both. We don’t set l to m because we’ve already evaluated m and confirmed that it’s not the maximum value.
Similarly, when nums[m] < nums[0], we ensure that m remains within the scope for the next iteration. This is because, if nums[m-1] happens to be the maximum value, it will only be identified when compared with its subsequent item which is nums[m].

Code Implementation in C++

class Solution {
public:
    int findPeakIdx(vector<int>& nums) {
        int l = 0, h = nums.size() - 1;
        while(l < h) {
            int m = l + (h-l)/2;
            if(nums[m] > nums[m+1]) {
                return m;
            }

            if(nums[m] > nums[0]) {
                l = m+1;
            }
            else {
                h = m;
            }
        }
        return -1;
    }
    int findMin(vector<int>& nums) {
        int peakIdx = findPeakIdx(nums);
        return nums[peakIdx+1];
    }
};

Detailed Breakdown of the Code:

`findPeakIdx()`:

This function takes a sorted rotated array nums and returns the index of the element at the peak (the point where the decreasing half starts). It uses binary search to achieve this:

l and h represent the left and right indices of the search space, respectively.
The loop continues until l < h .
m is calculated as the middle index.
If nums[m] is greater than nums[m+1], it signifies the peak is at m (the decreasing half starts after this point).
Otherwise, we need to determine which half holds the minimum element.

=> If nums[m] is greater than nums[0], the minimum element is likely in the right half (l = m+1).

=> Else, the minimum element is likely in the left half (h = m).

If the while loop doesn’t return any value from within, it implies that the last element is the maximum value in the array. In this case, we return -1 as the peakIdx.

`findMin()`:

This main function calls findPeakIdx to locate the peak index and then returns the element at the next index (peakIdx+1).

Dry Run with a Test Case

Let’s consider the test case nums = [11, 13, 15, 17]:

findMin calls findPeakIdx passing the input array

Inside`findPeakIdx()` :

Iteration 1(l < h):

loop starts with l = 0 and h = 3.
m is calculated to be 1
nums[m] = 13 is not > nums[m+1] = 15
nums[m] = 13 > nums[0] = 11 so l is updated to be m+1 = 2

Iteration 2(l < h):

l = 2, h = 3
m is calculated to be 2
nums[m] = 15 is not > nums[m+1] = 17
nums[m] = 15 > nums[0] = 11 so l is updated to be m+1 = 3

Iteration 3(l == h):

l = 3, h = 3
since l is not less than h, the while loop terminates and we return -1 from the findPeakIdx() function

Inside`findMin()` :

nums[peakIdx + 1] = nums[-1+1] = nums[0] = 11 is returned as the main output.

Time and Space Complexity Analysis

Time Complexity: The findPeakIdx function employs binary search, halving the search space in each iteration and resulting in a time complexity of O(log n), where n is the array’s size. findMin calls findPeakIdx once and then performs a constant-time operation to retrieve the minimum element, so the overall time complexity remains O(log n).
Space Complexity: The code uses constant extra space for variables like l, h, and m. This space complexity is independent of the input size and is considered O(1).

Real-World Applications

Circular Buffers: Circular buffers are used to store data where new elements are written at the end, and old ones are overwritten if the buffer is full. Finding the minimum element in a circular buffer with a sorted (but rotated) access pattern can be solved using this approach.
Log Analysis: Rotated logs might occur when a log file reaches its maximum size and starts overwriting older entries. To identify the most recent log entry (which might be the minimum based on timestamps), this technique can be employed.

Conclusion

The provided solution leverages binary search to efficiently find the minimum element in a sorted rotated array. This approach achieves a time complexity of O(log n) while utilizing constant extra space. Understanding the concept of rotated sorted arrays and applying binary search principles allows for efficient solutions in various real-world applications where data exhibits similar characteristics.

References

https://www.reddit.com/r/embedded/comments/1bg65qe/use_of_circular_buffer_in_embedded_systems/
https://www.digitalocean.com/community/tutorials/how-to-use-journalctl-to-view-and-manipulate-systemd-logs
Cover Photo by Elena Mozhvilo on Unsplash
Diagrams are made using Canva

What next?

If you’re intrigued by binary search algorithms, do check out my other posts where I delve into fascinating use cases that are solved using binary search:

Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array

Subhradeep Saha — Sat, 11 May 2024 03:17:37 +0000

Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 11, 2024 ・
Medium

Here is the Leetcode problem link - https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is a non-decreasing array.
-10^9 <= target <= 10^9

High-Level Approach

Binary search to the rescue

The brute force solution entails iterating through each item in the input array to determine the first and last indices of the specified target.

However, since the input is in non-decreasing order, we can leverage binary search to take advantage of this characteristic and significantly reduce the time complexity to a logarithmic scale.

How are we finding the indices?

The first index corresponds to either the beginning of the array or the position where the previous number is different from the target. Likewise, the last index corresponds to either the end of the array or the position where the next number is different from the target.

In cases where the target is not present in the input array, both indices’ positions are returned as -1.

Code Implementation in C++

class Solution {
public:
  int findIdx(vector<int>& nums, int target, bool firstIdxSearch) {
    int l = 0, h = nums.size() - 1;
    while (l <= h) {
      int m = l + (h - l) / 2;
      if (nums[m] > target) {
        h = m - 1;
      } 
      else if (nums[m] < target) {
        l = m + 1;
      } 
      else {
        if (!firstIdxSearch) {
          // Find last occurrence
          if ((m == nums.size() - 1) || (nums[m + 1] != target)) {
            return m;
          }
          l = m + 1;
        } 
        else {
          // Find first occurrence
          if (!m || (nums[m - 1] != target)) {
            return m;
          }
          h = m - 1;
        }
      }
    }
    return -1;
  }
  vector<int> searchRange(vector<int>& nums, int target) {
      int firstIdx = findIdx(nums, target, true);
      if (firstIdx == -1) {
        return {-1, -1};
      }
      return {firstIdx, findIdx(nums, target, false)};
  }
};

Breakdown of the Code

findIdx Function: This util function takes three arguments:

nums: The sorted array.
target: The value to search for.
firstIdxSearch: A boolean flag indicating whether to find the first or last occurrence of the target.

Binary Search Loop: The core logic resides within a while loop that continues as long as l (lower bound) is less than or equal to h (upper bound).

Inside the loop, m (middle index) is calculated.
The comparison between nums[m] and target determines the search direction:

=> If nums[m] > target, the target is in the lower half, so we update h to m-1.

=> If nums[m] < target, the target is in the upper half, so we update l to m+1.

=> If nums[m] == target, we've found a potential occurrence. The logic then diverges based on the firstIdx flag:

===> If firstIdxSearch is true (finding first occurrence), we check if this is truly the first by looking at nums[m-1] or is it at the beginning of the array. If not, we need to search in the left half (h = m-1).

===> Else, we check if this is the last by looking at nums[m+1] or is it at the end of the array. If not, we need to search in the right half (l = m+1).

Returning the Result:

If the loop completes without finding the target (l becomes greater than h), the function returns -1.
Otherwise, the function returns the index (m) of the found target occurrence, depending on whether it's the first or last based on the firstIdxSearch flag.

Dry Run with a Test Case

Let’s perform a dry run on the code using the example nums = [5,7,7,8,8,10] and target = 8:

Searching for First Occurrence (firstIdxSearch = true):

Iteration 1: l is set to 0, h is set to 5, and m is calculated as 2 (middle element):

Since nums[m] < target, we update l = m+1:

Iteration 2: Updated l = 3, h = 5 and m is calculated to be 4:

Now, nums[m] == target and nums[m-1] == target. So we update h as m — 1:

Iteration 3: Updated l = 3, h = 3 and m is calculated to be 3 as well:

Now, nums[m] == target and nums[m-1] != target, so we return m as the firstIdx.

Inside the main searchRange() function

After firstIdx is calculated to be not equal to -1, we proceed to again use the same findIdx() function to find the lastIdx of the target.

Searching for Last Occurrence (`firstIdxSearch` = false):

We call findIdx() again but now with the boolean firstIdxSearch set to false to find the last occurrence.

Iteration 1:l is set to 0, h is set to 5, and m is calculated as 2 (middle element):

Since nums[m] < target, we update l = m+1:

Iteration 2: Updated l = 3, h = 5 and m is calculated to be 4:

Now, nums[m] == target and nums[m+1] != target, so we return m as the lastIdx of the target.

Finally, we return {firstIdx = 3, lastIdx = 4} from the main function as the answer.

Complexity Analysis

Time Complexity: O(log n). The findIdx() function divides the search space into half with every iteration leading to a logarithmic time complexity in terms of n(the size of the input array).
Space Complexity: O(1). The code utilizes a constant amount of extra space for variables like l, h, and m, regardless of the array size (n).

Possible Improvements in the code

After the first findIdx() call, we obtain the index where the target is first found. Subsequently, for the second findIdx() call aimed at locating the last occurrence of the target, we can directly start the lower bound l as the output of the first findIdx() call instead of starting from 0. This is because we are certain that the target’s last occurrence cannot precede its first occurrence.

In the above example, when we call the findIdx() function to locate the last occurrence of the target (in this case, 8), we can optimize by using the output of the first call. This allows us to start processing directly from l = 3 (instead of l = 0) for the 2nd findIdx() function, thereby reducing the number of iterations required in the while loop.

Real-World Applications

Log File Search and Analysis: ystem logs often contain timestamped records of events or errors. These logs can be sorted chronologically. When troubleshooting issues or analyzing system behavior within a specific timeframe (e.g., identifying errors that occurred between 10:00 AM and 11:00 AM), binary search can be used to efficiently locate the relevant log entries within the sorted time range.
Financial Data Analysis and Trend Identification: Financial analysts might analyze historical stock prices which are often sorted chronologically. To identify periods where stock prices remained within a specific range (e.g., identifying days when a stock price stayed between $100 and $105), binary search can be applied to efficiently locate the relevant date ranges within the sorted price data.

Conclusion

This blog post delves into the problem of locating the initial and concluding positions of a target value within a sorted array. We explored the benefits of employing binary search for efficient searching, offer a comprehensive breakdown of the C++ code implementation, evaluated the time and space complexity, and investigated real-world applications of the given problem.

References

https://developers.cloudflare.com/logs/
https://www.quantconnect.com/learning/articles/introduction-to-financial-python
Diagrams are made using Canva
Cover Photo by Markus Winkler on Unsplash

What next?

If you’re intrigued by binary search algorithms, do check out my other posts where I delve into fascinating use cases that are solved using binary search.

Happy reading and happy coding!

Solving a Leetcode problem daily — Day 9 | First Bad Version

Subhradeep Saha — Thu, 09 May 2024 15:27:54 +0000

Solving a Leetcode problem daily — Day 9 | First Bad Version | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 9, 2024 ・
Medium

Here is the Leetcode problem link — First Bad Version

Problem Statement

Imagine you’re a product manager leading a software development team. During quality checks, you discover a bad version in your product. Since each version builds upon the previous one, any versions released after the bad one will also be faulty.

The challenge is to identify the first bad version as efficiently as possible. You’re given an array representing versions ([1, 2, ..., n]) and an API function isBadVersion(version) that returns true if the version is bad and false otherwise. The goal is to write a function that finds the index of the first bad version using the minimum number of API calls.

Example 1:

Input: n = 5, bad version at index 4
Output: 4

Explanation:

isBadVersion(3) returns false (version 3 is good).
isBadVersion(5) returns true (version 5 is bad).
Since version 4 is right before the first bad version (version 5), the answer is 4.

Example 2:

Input: n = 1, bad version at index 0 (only one version)
Output: 1

Explanation: The single version is bad, so the answer is 1.

Constraints:

1 <= bad <= n <= 2^31 - 1 (n is within the range of a 32-bit integer)

High-Level Approach

The direct method entails iterating from version 1 to n-1. If a version is good and the subsequent version is bad, we designate the next version as the solution. However, this could lead to calling isBadVersion() 2* (n-1)times(2 calls for each version from 2 to n-1and 1 call each for versions 1, n) at worst, potentially becoming inefficient for large n.

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
  int firstBadVersion(int n) {
    for(int x=1; x<=n-1; x++) {
        if(!isBadVersion(x) && isBadVersion(x+1)) {
            return x+1;
        }
     }
    return n;
  }
};

Reduce calls by using some space?

In the direct approach discussed above, it can be clearly seen that for every number from 2 to n-1, the call is made twice:

x = 1

x = 2

As seen above, there are redundant calls to isBadVersion(2). Perhaps we can optimize this by storing the calculated value during the initial run and then utilize the stored value for subsequent calls. This approach reduces the number of calls to just one for each number from 1 to n. However, the total no of calls still remains relatively high if n is very large.

Hint for Binary Search?

Since versions are ordered (1, 2, 3, …), bad versions will always cluster after the first bad version. Binary search allows us to exploit this ordering by repeatedly dividing the search space in half. We strategically pick a ‘middle’ version and use isBadVersion() for it and its next number. Based on the result, we can efficiently narrow down the search space to locate the first bad version.

Since with every iteration, we are dividing the search space by half, the number of calls to isBadVersion() drastically reduces to a complexity of O(log(n)) from the earlier complexity of O(n) .

Binary search is definitely a strategy to consider when dealing with sorted data. However, it’s worth noting that while binary search is effective for many such cases, it may not always be a perfect solution. Nevertheless, it remains a valuable option whenever we detect data sorted in some order.

Code Implementation(in C++)

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
  int firstBadVersion(int n) {
    int l = 1, h = n;
    while (l < h) {
      int m = l + (h - l) / 2;
      if (!isBadVersion(m) && isBadVersion(m + 1)) {
        return m + 1;
      }
      if (isBadVersion(m)) {
        h = m;
      } else {
        l = m;
      }
    }
    return l;
  }
};

Breakdown of the Code

Binary Search Initialization:

l (lower bound) is set to 1 (represents the first version).
h (upper bound) is set to n (represents the last version).
m (middle index) will be calculated during the search loop.

Binary Search Loop:

The while loop continues as long as l is less than h. This ensures the search space keeps narrowing down.

Inside the loop:

m is calculated as the middle index between l and h.
The key logic relies on two isBadVersion calls:
The first check is !isBadVersion(m) && isBadVersion(m + 1). This condition is true only if the middle version (m) is good (not bad) and the next version (m + 1) is bad. In this case, we've found the first bad version at index m + 1, and the loop terminates, returning this value.

Binary Search Refinement:

If the condition !isBadVersion(m) && isBadVersion(m + 1) isn't met, we need to refine the search space further.
If isBadVersion(m) is true (meaning m is bad), it signifies the first bad version could be within the lower half of the search space including m. We update h to m (excluding the upper half).
Conversely, if isBadVersion(m) is false (meaning m is good), the first bad version must lie in the upper half. We update l to m(excluding the lower half)

why updating l to m and not m+1? since in the while loop we check for the middle number to be good - that’s why we need to keep atleast 1 good version for the next iteration.

Returning the Result:

When the loop terminates (either by finding the first bad version or reaching the boundaries), the value of l is returned. Since the loop stops when l ≥ h, l will always point to the first bad version after the loop completes.

If the input nis 1, it means there’s only one version under consideration, which is then designated as the bad version. The code accommodates this scenario as well.

Further improvements in the code

One clear point of improvement is we can store the value of isBadVersion(m) in a boolean variable and reused instead of making one more call during the same iteration.
Another area for improvement involves storing the values of isBadVersion(m) and isBadVersion(m+1). This strategy helps us to reuse the previously checked version outputs, leading to a reduction in overall calls to the isBadVersion(version) function. However, it’s worth noting that Leetcode seems to be imposing space restrictions for larger values of n in this problem.

Dry Run with a Test Case

Let’s perform a dry run on the code using the example n = 5 and the first bad version as 3:

Initialization:

l is set to 1.
h is set to 5.
m is not yet calculated.

Iteration 1:

m is calculated as 3.
isBadVersion(m) (checking version 3) returns true.
isBadVersion(m+1) (checking version 4) returns true .
Since m is bad, we update h = m .

Iteration 2:

l = 1, h = 3
m is calculated to be 2
isBadVersion(m) (checking version 2) returns false.
isBadVersion(m+1) (checking version 3) returns true thereby returning m+1 = 3 as the first bad version

Time and Space Complexity Analysis

Time Complexity: O(log n). The binary search approach significantly reduces the number of API calls needed to locate the first bad version. With each iteration, the search space is halved, leading to a logarithmic time complexity in terms of n.
Space Complexity: O(1). The code utilizes a constant amount of extra space for variables like l, h, and m, regardless of the input size n. This makes the solution memory-efficient.

Conclusion

This blog post explored how Binary search can be used to solve Leetcode’s First Bad Version problem. We delved into the details of the problem statement and found out how Binary search can be thought of as an option whenever the problem contains some data ordered in a predictable way. Time complexity get reduced to a much smaller logarithmic scale thereby improving the solution’s efficiency by a whole margin.

References

Cover photo by Agence Olloweb on Unsplash
Diagrams in the Dry run section are created using Canva

If you liked this post, do applaude by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha for such posts.

If you want to follow on with binary search problems, do consider reading this post https://blog.devgenius.io/solving-a-leetcode-problem-daily-day-8-sqrt-x-5e2521ef6fbe where I explained how binary search can be used to efficiently find the square root of a number — there is 1 Math hack as well described in the post about square roots so dont forget to checkout and applaude that post. Thanks!!

Solving a Leetcode problem daily — Day 8 | Sqrt(x)

Subhradeep Saha — Tue, 07 May 2024 13:25:38 +0000

Solving a Leetcode problem daily — Day 8 | Sqrt(x) | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 7, 2024 ・
Medium

Here is the Leetcode problem link — Sqrt(x)

Problem Statement

LeetCode presents a challenge where you’re given a non-negative integer x and the task is to write a function that returns the integer square root of x rounded down to the nearest whole number.

This calculation must be performed without relying on built-in functions like pow(x, 0.5) (C++) or x ** 0.5 (Python).

Example:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down 
to the nearest integer, 2 is returned.

Constraints:

x can range from 0 to the maximum possible value for an integer data type (2^31 - 1).

High Level Approach

At first, the instinctive approach to solving the problem involves using a language’s built-in function to find the square root. However, this method does not align with the problem definition. The second apparent approach that comes to mind is finding the square root by iterating through every number from 1 to x. However, the most optimal solution, which we will discuss in this blog offers a more efficient approach.

The high-level concept of the optimal approach is as follows:

For any number x, the square root of x is always ≤ x/2
By employing binary search within the range of 1 to x/2, we check whether the middle number is the square root or not. If not, we narrow down the search space for the next iteration by comparing the square of the middle number with the input x

Code Implementation

class Solution {
public:
  int mySqrt(int x) {
    if (!x || x == 1) { 
      return x;
    }
    int l = 1, h = x / 2, m; 

    while (l <= h) { 
      m = l + (h - l) / 2; 

      long prod = (long) m * m; 

      if (prod == x) { 
        return m;
      }

      if (prod > x) { 
        h = m - 1;
      } else { 
        l = m + 1;
      }
    }

    return h;
  }
};

Breakdown of the Code

This code defines a class Solution with a function mySqrt that takes the integer x as input and returns the integer square root rounded down.

Edge Case Handling:

The code first checks for edge cases:

If x is 0, it returns 0 (square root of 0 is 0).
If x is 1, it returns 1 (square root of 1 is 1).

Binary Search Initialization:

Three integer variables are declared:

l (lower bound) initialized to 1.
h (upper bound) initialized to x / 2 (considering the largest possible square root for the given x).
m (middle index) will be used during the search.

Binary Search Loop:

A while loop iterates as long as l is less than or equal to h. This ensures the search space keeps narrowing down.

Inside the loop:

m is calculated as the middle index between l and h — m is calculated indirectly to prevent integer overflow due to l + h
prod is calculated by squaring the m value, but using long to prevent integer overflow for larger values of x.
If prod is equal to x, it means we've found the exact square root, and the loop terminates, returning m.

Value Comparison and Search Refinement:

If prod is greater than x, it indicates the middle value (m) is too high. The upper bound (h) is updated to m - 1 to focus the search on the lower half of the range.
If prod is less than x, it indicates the middle value (m) is too low. The lower bound (l) is updated to m + 1 to search the upper half of the range.

Returning the Result:

We encounter two scenarios for returning the result:

The first occurs when we find the exact square root inside the while loop, leading to an immediate return.
In the second case, if we do not find the exact square root, the while loop terminates, and the value of h is returned.

Now, why do we specifically return hand not l, m, or any other number?

The loop halts when l exceeds h, guaranteeing that his always one less than a number whose square root is greater than x. This ensures that we return the integer rounded down, as specified in the problem statement.

=> If the problem were to require returning the closest possible square root rounded up, we would return l instead of h.

=> Similarly, if the problem mandated returning -1 when an exact square root isn’t found, we would return -1instead of h.

Complexity Analysis

Time Complexity

The time complexity of the binary search solution for finding the integer square root is O(logn), where n is the input number x. Here's a breakdown of why:

Binary Search: The algorithm employs binary search, which repeatedly halves the search space with each iteration. This process of dividing the space ensures significant reduction in the number of comparisons needed to locate the target value.
Logarithmic Iterations: The number of iterations required to traverse the search space using binary search is roughly proportional to the logarithm of the initial search space size (base 2). In this case, the initial space ranges from 1 to x / 2, which is logarithmic in terms of x.

Therefore, the time complexity grows logarithmically with the increase in the input value x, making the solution efficient for handling larger numbers.

Space Complexity

The space complexity of the binary search solution is O(1), which is considered constant space complexity. Here’s why:

Limited Variables: The algorithm utilizes a fixed number of variables to store essential data like loop counters, indices, and temporary values. These variables do not depend on the input size x.
No Additional Data Structures: The solution doesn’t involve creating or manipulating any additional data structures like arrays or lists whose sizes would scale with the input.

Because the space complexity remains constant regardless of the input size, the solution is memory-efficient.

Dry Run with a Test Case

Let’s perform a dry run on the code using the example x = 8:

Edge Case Check: Since x is not 0 or 1, the code proceeds.
Initialization:

l is set to 1.
h is set to 4(half of 2).
m is not yet calculated

3. Iteration 1:

m is calculated as 1 + (4 — 1)/2 = 2.
prod is calculated as 2 * 2 = 4.
Since prod is less than x, l is updated to m + 1 (which becomes 3).

4. Iteration 2:

l = 3 is still less than h= 4
m is calculated as 3 + (4 — 3)/2 = 3.
prod is calculated as 3 * 3 = 9.
Since prod is greater x, h is updated to m — 1 = 2

4. Iteration 3:

l = 3 is now greater than h = 2, so the while loop terminates now

5. Result: The function returns h (which is 2), representing the integer square root of 8 rounded down (as expected).

Real-World Applications

Finding the integer square root without built-in functions has various real-world applications:

Game Development: In video games, calculating distances, applying physics simulations, or generating random numbers can involve square root computations. Using an efficient custom implementation like this can be beneficial, especially for performance optimization in resource-constrained environments.
Cryptography: Some encryption algorithms rely on modular arithmetic operations, which might involve square root calculations. Implementing a custom square root function can provide more control over the algorithm’s behavior, potentially enhancing security.
Embedded Systems: In microcontrollers or other embedded systems with limited processing power and memory, using a custom square root function can be more efficient than relying on bulky libraries with built-in math functions.

Conclusion

This blog post delved into essential concepts such as square root constraints and the application of the binary search algorithm to address problems where search spaces can be minimized for subsequent iterations, thereby reducing time complexities from O(n) to O(logn). Grasping this approach can prove invaluable in scenarios demanding efficient square root calculations without dependence on external libraries.

References

Game Development with Physics: https://www.new3jcn.com/simulation.html
Introduction to Cryptography: https://www.khanacademy.org/computing/computer-science/cryptography
Introduction to Embedded Systems: https://www.amazon.com/Embedded-Systems-Architecture-Programming-Engineering/dp/007340456X
Diagrams in the Dry run section are created using Canva
Cover photo by Antoine Dautry on Unsplash

If you liked this post, do applaude by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha for such posts. If you are a Maths + Coding enthusiast, then do checkout these Medium posts of mine solving other Leetcode problems related to Math and Arrays —

Solving a Leetcode problem daily — Day 6 | Longest Common Prefix

Subhradeep Saha — Mon, 06 May 2024 02:33:10 +0000

Solving a Leetcode problem daily — Day 6 | Longest Common Prefix | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 4, 2024 ・
Medium

Conquering LeetCode: Finding the Longest Common Prefix

This blog post tackles a classic LeetCode challenge: given an array of strings, write a function that finds the longest string which is a prefix (beginning) of all the strings in the array. We’ll delve into the problem statement, code implementation, step-by-step explanation, real-world applications, and conclude with some key takeaways.

Here is the Leetcode problem link —

https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1162/

Problem Statement

LeetCode presents a challenge where you’re given an array of strings (strs). The task is to write a function that returns the longest common prefix shared by all strings in the array.

Example:

Input: strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation:: Here, "fl" is the longest prefix that appears at the beginning 
of all three strings.

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

The number of strings (strs.length) can range from 1 to 200.
The length of each individual string (strs[i].length) can range from 0 to 200.
All characters in the strings are lowercase English letters.

Code Implementation

Here’s the C++ code that solves this challenge:

class Solution {
public:
  string longestCommonPrefix(vector<string>& strs) {
      if (strs.size() == 1) {
        return strs[0]; 
      }

      string pref = "";
      int currIdx = 0;

      while (1) {
        char ch;
        for (int i = 0; i < strs.size(); i++) {
          string s = strs[i];

          if (currIdx >= s.length()) { 
            return pref;
          }

          if (i == 0) { 
            ch = s[currIdx];
          }

          if (s[currIdx] != ch) { 
            return pref;
          }
        }
        pref += strs[0][currIdx++]; 
      }
      return pref;
  }
};

Breakdown of the Code

This code defines a class Solution with a function longestCommonPrefix that takes the array of strings (strs) as input and returns the longest common prefix.

Edge Case: The code first checks if there’s only one string (strs.size() == 1) in the input array. In that case, the single string itself is the longest common prefix, so it's returning that(return strs[0]).
Initialization:

pref (empty string) stores the growing common prefix.
currIdx (integer) keeps track of the current index (position) within the strings being compared.

3. Looping and Comparison:

An infinite while(1) loop continues until the common prefix is found or there's a mismatch.

Inside the loop:

A character variable ch is declared to hold the character to be compared across all strings.
A for loop iterates through each string (strs[i]) in the array.
If currIdx reaches the end of the current string (currIdx >= s.length()), it means there's no more prefix to compare, so the current pref is returned.
In the first iteration (i == 0), the character at currIdx from the first string (strs[0]) is assigned to ch as the reference point for comparison.
If the character at currIdx in the current string (s[currIdx]) doesn't match the reference character ch, it indicates a mismatch, and the loop terminates, returning the current pref.

4. Building the Prefix:

If all characters at currIdx across all strings match, the character from strs[0] at currIdx is appended to the pref string and simultaneously the currIdx is also incremented to move to the next character position for the next iteration. (pref += strs[0][currIdx++])

5. Return Value:

The loop eventually breaks when a mismatch is found between the strings character at currIdx or we reached the end of any of the string. The final pref string containing the longest common prefix is returned.

Lets verify the code with a dry run of a testcase in the next section

Code Dry Run with a Test Case

Let’s use the provided example:

Input: strs = ["flower", "flow", "flight"]

Step 1: Edge Case Check (Skipped)

There are more than one string, so the code proceeds to the main logic.

Step 2: Initialization

pref = "" (empty string)
currIdx = 0

Step 3: Loop Iteration 1

Character Comparison:

ch is assigned the first character from the first string (ch = 'f')
All three strings have ‘f’ at index 0, so the loop continues.

Building the Prefix:

‘f’ is appended to pref: pref = "f"
currIdx is incremented to 1 (currIdx = 1)

Step 4: Loop Iteration 2

Character Comparison:

All three strings have ‘l’ at index 1, so the loop continues.

Building the Prefix:

‘l’ is appended to pref: pref = "fl"
currIdx is incremented to 2 (currIdx = 2)

Step 5: Loop Termination (Mismatch)

Character Comparison:

The third string (“flight”) has ‘i’ at index 2, while the first two strings have ‘o’. There’s a mismatch.

The loop terminates at this point.

Result:

The final value of pref is "fl", which is the longest common prefix for all three strings. The function returns "fl".

Real-World Applications

Finding the longest common prefix has various applications in real-world scenarios:

File Compression: In data compression techniques like Lempel-Ziv coding, the longest common prefix between repeated strings can be identified and replaced with a reference, reducing file size.
Autocompletion: Search engines and text editors often use the longest common prefix to suggest completions for partially typed words, improving user experience.
Natural Language Processing (NLP): NLP tasks like text classification or stemming (reducing words to their base forms) can utilize common prefixes to group related words or identify word stems.

Conclusion

This blog post explored the LeetCode challenge of finding the longest common prefix using a C++ code. We broke down the problem statement, presented the code with detailed step-by-step explanations, performed a dry run with a test case and discussed real-world applications.

References

File Compression (Lempel-Ziv Coding):https://ethw.org/Milestones:Lempel-Ziv_Data_Compression_Algorithm,_1977 by Wikipedia: This article provides an overview of Lempel-Ziv (LZ) coding, a family of data compression algorithms. It mentions that LZ77, a specific variant, uses the concept of finding repeating phrases and replacing them with references to a dictionary, effectively using longest common prefixes for compression.
Autocompletion:https://searchengineland.com/how-google-autocomplete-works-390257 by Google Research: This blog post discusses various techniques used in search query autocomplete. It mentions that a prefix tree data structure can be employed to efficiently identify prefixes of words stored in the system, enabling suggestions based on the common prefix typed by the user.
Natural Language Processing (NLP):https://en.wikipedia.org/wiki/Stemming by Wikipedia: This article describes stemming algorithms, a technique in NLP used to reduce words to their base forms. Some stemming algorithms, like the Porter Stemmer, rely on identifying common prefixes among words to achieve stemming.
The diagrams in the Dry run section are created using Canva.

If you liked this blog, do applaude by clicking on the clap hands icon and drop down any feedback you have in the comments.

You can follow me https://medium.com/@subhradeep_saha and check out my other posts as well where I explained the solutions of few other interesting Leetcode problems:

Solving a Leetcode problem daily — Day 5 | Diagonal Traverse

Subhradeep Saha — Mon, 06 May 2024 02:32:51 +0000

Solving a Leetcode problem daily — Day 5 | Diagonal Traverse | by Subhradeep Saha | May, 2024 | Dev Genius

Slay Leetcode’s Diagonal Traversal problem with this detailed C++ guide - code breakdown, dry run with diagrams, & real-world applications.

blog.devgenius.io

Here is the Leetcode problem:

https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1167/

Problem Statement

Given a matrix (mat) with dimensions m x n (rows and columns) the task is to write a function that returns a one-dimensional array containing all the elements of the matrix in a diagonal order.

Example:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,4,7,5,3,6,8,9]

Here, the elements are traversed diagonally, starting from the top-left corner and moving towards the bottom-right corner (direction is ↘), zig-zagging between upward and downward diagonals.

Constraints:

The number of rows (m) is equal to the length of the inner arrays (mat.length).
The number of columns (n) is equal to the length of each inner array (mat[i].length).
Both m and n can range from 1 to 10^4 (10,000).
The total number of elements (m * n) can also range from 1 to 10^4.
Individual elements in the matrix (mat[i][j]) can have values between -10^5 and 10^5 (inclusive).

Code Implementation

Here’s the C++ code that solves this challenge:

class Solution {
public:
  vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    int left_r = 0, left_c = 0, right_r = 0, right_c = 0;
    int r = mat.size(), c = mat[0].size();
    bool traverseRight = true;
    vector<int> res;

    while (left_c != c && left_r != r && right_c != c && right_r != r) {
        traverse(mat, traverseRight, left_r, left_c, right_r, right_c, res);

        if (left_r + 1 < r) {
            left_r++;
        } 
        else {
            left_c++;
        }

        if (right_c + 1 < c) {
          right_c++;
        } 
        else {
          right_r++;
        }

        traverseRight = !traverseRight;
    }
    return res;
  }
private:
  void traverse(vector<vector<int>>& mat, bool traverseRight, int left_r, int left_c, int right_r, int right_c, vector<int>& res) {
    if (traverseRight) {
      while (left_r >= right_r) {
        res.push_back(mat[left_r--][left_c++]);
      }
    } 
    else {
      while (left_r >= right_r) {
        res.push_back(mat[right_r++][right_c--]);
      }
    }
  }
};

Breakdown of the Code

This code defines a class Solution with two functions:

findDiagonalOrder: This is the main function that takes the matrix (mat) as input and returns the diagonal order array (res).
traverse: This is a helper function that performs the diagonal traversal based on a direction flag (traverseRight) and boundary indices (left_r, left_c, right_r, right_c).

Initialization:

[left_r, left_c] and [right_r, right_c] are the 2 boundary items on a diagonal between which we need to traverse. The first one is the boundary item on the left of the diagonal and the other is on the right boundary.
r stores the number of rows (mat.size()).
c stores the number of columns (mat[0].size()).
traverseRight Flag**:** This boolean variable controls the direction of traversal.

true: Indicates right-upward diagonal traversal ([left_r, left_c] to [right_r, right_c])

false: Indicates left-downward diagonal traversal ([right_r, right_c] to [left_r, left_c]).

res: This vector stores the elements of the matrix in diagonal order as they are traversed.
while loop: The core logic resides within this loop, which continues until all elements are processed. It checks if any of the indices (left_c, left_r, right_c, right_r) reach their respective matrix boundaries.
traverse function: Inside the loop, the traverse helper function is called based on the current traverseRight flag. This function handles the actual diagonal element addition to the res vector based on the traverseRight flag.
Updating Indices: After each iteration of the traverse function:

a) If there are still more elements in the current row (left_r + 1 < r), left_r is incremented (moving down).

b) Otherwise, left_c is incremented (moving right to the next column).

c) If there are items in the current column(right_c + 1 < c), we got to next column right_c++ else we go 1 row down(right_r++).

d) Toggling Direction: Finally, the traverseRight flag is flipped (!traverseRight) to indicate a change in direction for the next iteration.

traverseFunction: This helper function takes several arguments:

mat: The reference to the original matrix.
traverseRight: The direction flag.
Boundary indices (left_r, left_c, right_r, right_c): Define the starting and ending points for the current diagonal traversal.
res: The reference to the result vector.
Inside the traverse function, a while loop continues as long as all the items in the diagonal are pushed to the res vector.
Based on the traverseRight flag:

=> If true (upward diagonal): elements from mat[left_r][left_r] are added to res ; left_r is decremented and left_c is incremented to indicate a diagonally right-upward movement

=> If false (downward diagonal): elements from mat[right_r][right_c] are added to res ; right_r is incremented and right_c is decremented implying a diagonally left-downward movement.

Return Value: The findDiagonalOrder function returns the final res vector containing all the matrix elements in diagonal order.

Dry Run with a Test Case

Let’s use the provided example matrix:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

Step 1: Initialization

left_r = 0, left_c = 0 (left side of a diagonal)
right_r = 0, right_c = 0 (right side of the diagonal)
r = 3 (number of rows)
c = 3 (number of columns)
traverseRight = true (initial upward diagonal)
res = [] (empty result vector)

Step 2: First Iteration (Upward Diagonal)

We call the traverse function with traverseRight = true. It starts processing elements from mat[0][0] (1) and moves diagonally up until it reaches the boundary (left_r < right_r).

res = [1] (1 added to res)

Step 3: Updating Indices

Since there are more elements in the first row (left_r + 1 < r), we increment left_r to 1. Similarly we increment right_c to 1. Hence our next diagonal boundaries are ready:

left_r = 1, left_c = 0
right_r = 0, right_c = 1

The traverseRight flag is now reversed to false indicating a left-downward diagonal movement

Step 4: Second Iteration (Left-Downward Diagonal)

We call traverse again. This time, it moves diagonally left-down.

res = [1, 2, 4]

Step 5: Updating Indices

Same logic as Step 3

left_r = 2, left_c = 0
right_r = 0, right_c = 2

The traverseRight flag is now reversed to true indicating a right-upward diagonal movement.

Step 6: Third Iteration (Right-Upward Diagonal)

res = [1, 2, 4, 7, 5, 3]

Step 7: Updating Indices

For right boundary, there are no more elements in the current column (right_c + 1 > c), so we increment right_r to move down. Similarly for left boundary, there are no more items in the current row, so we move right by incrementing left_c

left_r = 2, left_c = 1
right_r = 1, right_c = 2

Step 8: Fourth Iteration (Left-Downward Diagonal)

res = [1, 2, 4, 7, 5, 3, 6, 8]

Step 9: Updating Indices

Same as step 7

left_r = 2, left_c = 2
right_r = 2, right_c = 2 (reaches the end of the last row)

Step 10: Fifth Iteration (Upward Diagonal)

res = [1, 2, 4, 7, 5, 3, 6, 8, 9]

Step 11: Updating Indices

Same as step 7

left_r = 2, left_c = 3
right_r = 3, right_c = 2

Step 12: Loop Termination

The diagonal boundary is getting out of the actual input matrix dimensions so the while loop gets terminated.

Final Result:

The res vector now contains all the elements of the matrix in diagonal order: [1, 2, 4, 7, 5, 3, 6, 8, 9].

Real-World Applications

This diagonal order traversal technique can be applied to various real-world scenarios:

Image Processing: When processing images, diagonal filtering techniques can be used for noise reduction or edge detection. By iterating over pixels in a diagonal order, filters can analyze neighboring pixels along diagonal patterns for specific effects.
Game Development: In certain game genres like strategy games, pathfinding algorithms might consider diagonal movement for characters. Traversing the game map diagonally can help identify potential paths or obstacles.
Machine Learning: In some machine learning algorithms, diagonal traversal can be used to access and process data stored in matrices. This can be relevant for tasks like image recognition or natural language processing.

Conclusion

This blog explored the LeetCode challenge of traversing the diagonals of a matrix in C++. We tackled the problem statement, presented the code with explanations, performed a dry run with a test case and discussed few real-world applications.

References

“Bilateral Filtering for Noise Reduction in Digital Images”https://people.csail.mit.edu/fredo/PUBLI/Siggraph2002/DurandBilateral.pdf by Sylvain Paris and Pierre Kornprobst: This paper explores bilateral filtering, a technique used for noise reduction in images. It mentions that bilateral filters can be applied along different directions, including diagonals.
“Pathfinding with Grids”https://brianlovin.com/hn/34594547 by Christer Eklund on Gamasutra: This article discusses various pathfinding techniques for grid-based game worlds. It mentions that diagonal movement can be an important factor for characters to navigate efficiently within the game environment.
“Convolutional Neural Networks for Visual Recognition”https://cs231n.github.io/ by Andrej Karpathy et al.: CNNs heavily rely on matrix operations, and diagonal traversal can be a relevant concept for accessing and processing data within these matrices.
Matrix diagrams are created using Canva

If you liked this blog, do applaude the post by clicking on the clap hands icon. You can follow me https://medium.com/@subhradeep_saha and check out my other posts as well. In case you are interested more on traversals, do checkout this post — Spiral Matrix Traversal, where I explained the spiral traversal of a matrix. Thanks!

Solving a Leetcode problem daily — Day 4 | Add Binary

Subhradeep Saha — Mon, 06 May 2024 02:32:24 +0000

Solving a Leetcode problem daily — Day 4 | Add Binary | by Subhradeep Saha | Medium

Subhradeep Saha ・ Apr 30, 2024 ・
Medium

Here is the leetcode problem link — https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1160/

1. Problem Statement, Constraints, and Test Case

Problem: Write a function that takes two binary strings (a and b) as input and returns their sum, also represented as a binary string.

Constraints:

The length of each string (a and b) can range from 1 to 10^4 (10,000) characters.
Both strings consist only of ‘0’ or ‘1’ characters.
There are no leading zeros (except for the single digit “0” itself).

Test Case:

Input: a = "11", b = "1"
Expected Output: “100” (Equivalent to 4 in decimal)

2. Code

class Solution {
public:
  int binToInt(char a) {
    return a == '1';
  }

  void calculateSumCarryRes(int& carry, int arrSum, string& res) {
    int sum = arrSum + carry;
    carry = sum / 2;
    res = to_string(sum % 2) + res;
  }

  string addBinary(string a, string b) {
    string res = "";
    int i = a.length() - 1, j = b.length() - 1;
    int carry = 0;

    while (i >= 0 && j >= 0) {
      calculateSumCarryRes(carry, binToInt(a[i]) + binToInt(b[j]), res);
      i--;
      j--;
    }

    while (i >= 0) {
      calculateSumCarryRes(carry, binToInt(a[i]), res);
      i--;
    }

    while (j >= 0) {
      calculateSumCarryRes(carry, binToInt(b[j]), res);
      j--;
    }

    if (carry) {
      res = to_string(carry) + res;
    }

    return res == "" ? "0" : res;
  }
};

3. Logic Behind Solving the Problem

Overflow errors will come in case we try to convert the binary strings to decimal numbers => add those => convert the sum to a binary string and return it

We solve this problem by simulating the manual addition process used for decimal numbers. However, since we’re dealing with binary (only 0s and 1s), the process is slightly different. Here’s the core logic:

Convert characters to numbers: We need to convert the binary characters (‘0’ or ‘1’) to their corresponding numerical values (0 or 1).
Add corresponding digits: Add the current digits from both strings and handle carry-over.
Carry-over logic: If the sum of two digits is greater than or equal to 2, there’s a carry-over of 1 to the next digit. In binary, any value greater than 1 results in a carry-over.
Build the result string: Append the remainder of the sum (either 0 or 1) to the beginning of the result string. Since we’re adding digits in reverse order (starting from the least significant bit), this builds the result correctly.

4. Detailed Explanation of the Code (Line by Line)

a. Helper Functions:

binToInt(char a): This function takes a character (a) as input and returns 1 if it's '1', otherwise it returns 0. It simply converts the binary character to its numerical value.
calculateSumCarryRes(int& carry, int arrSum, string& res): This function calculates the sum, carry, and result digit for a single addition step.

i) It takes three arguments by reference: carry (integer to store carry-over), arrSum (the sum of current digit values), and res (string to store the result).

ii) It calculates the total sum by adding carry and arrSum.

iii) It updates the carry value by dividing the sum by 2 (since we're in binary).

iv) It appends the remainder of the sum divided by 2 (which will be 0 or 1) to the beginning of the res string using to_string and the + operator.

b. Main Function:

addBinary(string a, string b): This is the main function that handles the entire binary addition process.

Initialization:

Initializes an empty string res to store the final result.
Creates variables i and j as pointers to iterate through the last characters (indices) of strings a and b, respectively.
Initializes carry to 0 to handle potential carry-over from the addition process.

Main While loop:

Uses a while loop that iterates as long as both i and j are within the valid range of their respective strings (i.e., not negative):
Calls the calculateSumCarryRes function to calculate the sum, carry, and append the result digit to res. This essentially adds the corresponding digits from both strings and handles carry-over.
Decrements i and j to move on to the next characters in the strings.

Additional while loops for input strings of different sizes:

The first loop iterates through the remaining characters of a (if i is still positive) using the same logic as the main loop (calling calculateSumCarryRes). This adds any remaining digits from the longer string a.
The second loop iterates through the remaining characters of b (if j is still positive) using the same logic (calling calculateSumCarryRes). This adds any remaining digits from the longer string b.

Handling carry over:

If there’s a carry-over left after processing all the digits (carry is not 0), it's appended to the beginning of res using to_string and the + operator.

Edge case handling:

At the end lies a ternary operator that checks if res is empty (meaning both input strings were "0"). If so, it returns "0" to ensure a valid output (empty string is not be the expected output behaviour).

5. Walkthrough of the Code for a Test Case

Input:a = "11", b = "1"

Step-by-Step Breakdown:

Initialization:res is empty, i = 1 (pointing to the last character of "11"), j = 0 (pointing to the last character of "1"), carry = 0.
Main Loop:

Iteration 1:

Add binToInt(a[i]) (1) and binToInt(b[j]) (1), resulting in a sum of 2.
Since the sum is greater than or equal to 2, there’s a carry-over of 1 (carry is updated to 1).
The remainder of the sum divided by 2 (which is 0) is appended to res (initially empty, becomes "0").
Decrement i and j.

Remaining Digits ofa:

Add binToInt(a[i]) (1) and carry (1), resulting in a sum of 2.

Similar to the previous iteration, carry-over is 1 and the remainder (0) is appended to res (becomes "00").
Decrement i. Since j is already -1 (out of bounds), the second while loop for remaining digits of b is skipped.

Carry-Over Handling:

Since carry is still 1 after processing all digits, it's appended to the beginning of res resulting in the final output: res = "100".

Output: “100” (Equivalent to 4 in decimal)

6. Real-Life Applications of this Problem

While adding binary strings might seem like a theoretical exercise, it has several practical applications in the world of computers:

Computer Arithmetic: Binary addition forms the core of arithmetic operations in computers. CPUs use binary addition circuits to perform calculations like addition, subtraction, multiplication, and division on binary numbers representing data.
Error Detection and Correction: Communication protocols often employ techniques like checksums or parity bits to detect errors during data transmission. These techniques rely on binary addition to create a redundant value that can be compared to the received data to identify inconsistencies.
Computer Graphics: Binary addition plays a role in various aspects of computer graphics, such as color representation and image manipulation. Algorithms for blending colors or manipulating pixel values often involve binary addition operations.

By understanding binary addition, we gain a deeper insight into how computers perform calculations, handle data, and implement various functionalities. It’s a foundational concept in computer science and essential for anyone interested in how computers work at the core level.

7. Conclusion

This blog post has explored the challenge of adding binary strings in C++. I have broken down the problem statement, code, logic, and real-world applications. Feel free to experiment with different test cases and challenge yourself further!

If you liked this post, do applaude this story by clicking on the clap hands button and follow me https://medium.com/@subhradeep_saha. You can checkout my other Leetcode problem explanation posts in my profile page.

Do let me know in the comments in case of any feedback you have for the article. Thanks!

Solving a Leetcode problem daily - Day 7 | Array Partition I

Subhradeep Saha — Mon, 06 May 2024 02:30:00 +0000

Solving a Leetcode problem daily — Day 7 | Array Partition I | by Subhradeep Saha | Medium

Subhradeep Saha ・ May 6, 2024 ・
Medium

Here is the Leetcode problem link — Array Partition I

Problem Statement

LeetCode presents a challenge where you’re given an integer array nums containing 2n elements. The objective is to group these elements into n pairs, where n is half the array size. Each pair consists of two elements ((a_i, b_i)) from the array. The goal is to maximize the sum obtained by adding the minimum value (min(a_i, b_i)) within each pair.

Example:

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

Explanation: There are three possible pairings:

(1, 4), (2, 3): Sum of minimums = 1 + 2 = 3
(1, 3), (2, 4): Sum of minimums = 1 + 2 = 3
(1, 2), (3, 4): Sum of minimums = 1 + 3 = 4

The optimal pairing is (1, 2) and (3, 4), resulting in a maximum sum of 4.

Constraints:

The number of pairs (n) ranges from 1 to 10^4.
The array size (nums.length) is always even (2n).
Individual elements in the array (nums[i]) can range from -10^4 to 10^4.

High level approach

The problem looks to be complex at first glance but if we analyse the pattern of the optimal pairs, for a pair — the larger number gets sacrificed for the smaller one. To maximize the sum, we need to have the least difference between the numbers of a pair — so that for a pair, we don’t sacrifice a much bigger number.

Sorting helps us reduce the difference between the numbers of a pair and we ensure for every pair (a_i, b_i) , b_i is the least one that we sacrifice among all of the other numbers.

Code Implementation

class Solution {
public:
  int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end()); 
    int ans = 0;
    for (int i = 0; i < nums.size(); i += 2) {
      ans += nums[i];
    }
    return ans;
  }
};

Breakdown of the Code

Class and Function definition:

The code defines a class Solution with a function arrayPairSum that takes the integer array nums as input and returns the maximized sum of minimum values in pairs.

Sorting:

The sort function is used to arrange all elements in the nums array in ascending order. This step is crucial because we want to pair the smallest elements with the next larger elements to maximize the minimum value within each pair.

Iterating and Adding:

An integer variable ans is initialized to 0 to store the accumulated sum.
A for loop iterates through the sorted array nums with a step size of 2 (i += 2). This step size ensures we only consider the first element (minimum value) from each pair.
Inside the loop, the value at the current index i (the minimum value in the current pair) is added to the ans variable.

Returning the Sum:

After iterating through all pairs, the final value of ans represents the maximized sum of minimum values, which is returned by the function.

Dry Run with a Test Case

Let’s use the provided example:

Input: nums = [1, 4, 3, 2]

Sorting: First, the array is sorted: [1, 2, 3, 4].

Iteration:

Loop starts at i = 0 (index of the first element, which is 1).
ans is incremented by nums[i] (1).
Loop continues to i = 2 (index of the third element, which is 3).
ans is again incremented by nums[i] (3).
The loop terminates as it has considered all pairs (first and third elements).

Result: The final value of ans is 4 (1 + 3) — 1 from the first pair and 3 from the second pair. This matches the expected output for the given test case.

Real-World Applications

This concept of maximizing the minimum value in pairings can be applied in various real-world scenarios:

Resource Allocation: When assigning resources (like budget, personnel, or materials) to multiple tasks or projects, this approach can help ensure that even the least-resourced projects receive enough to function at a base level, maximizing overall efficiency.
Inventory Management: In managing inventory, prioritizing the sale of items with the lowest profit margin alongside items with higher margins can help clear out slow-moving stock while still generating some revenue.
Network Optimization: In network routing algorithms, this strategy can be used to ensure that even the least efficient connections (with lower bandwidth) are paired with connections with higher bandwidth, optimizing overall network traffic flow.

Conclusion

This blog post explored the LeetCode challenge of maximizing the sum of minimum values in pairs. We tackled the problem statement by getting to understand how sorting helps in solving the problem, presented and explained the C++ code, performed a dry run with a test case and discussed a few real-world applications of this problem.

References

Resource Allocation: https://www.pmi.org/learning/library/resource-allocation-5304
Inventory Management: https://www.investopedia.com/bullwhip-effect-definition-5499228
Network Optimization: https://en.wikipedia.org/wiki/Category:Routing_algorithms
Cover Photo by Nick Hillier on Unsplash

If you liked this post, do applaude the post by clicking on the clap hands icon and follow me https://medium.com/@subhradeep_saha as well. Do checkout my other posts in my profile and let me know if you have any feedback. Thanks!

Solving a Leetcode problem daily — Day 3: Spiral Matrix

Subhradeep Saha — Sun, 05 May 2024 18:30:00 +0000

Solving a Leetcode problem daily — Day 3: Spiral Matrix | by Subhradeep Saha | Apr, 2024 | Medium

Subhradeep Saha ・ Apr 28, 2024 ・
Medium

Here is the Leetcode problem - Spiral Matrix

Problem Statement

Given a two-dimensional matrix (matrix), where each element represents a number, the task is to write a function that returns a new list containing all the elements of the matrix traversed in a spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

What We Want to Achieve

This problem aims to develop a function that iterates through a matrix in a specific pattern, ensuring:

Every element is visited once: No number in the matrix is left untouched.
Spiral Path: The traversal follows a clockwise spiral path, starting from the top-left corner and gradually moving inwards.
Resultant List: The function returns a new list containing all the elements of the matrix in the order they were visited during the spiral traversal.

The Code

Here’s the complete C++ code that tackles this challenge:

class Solution {
public:
    void traverse(vector<int>& res, vector<vector<int>>& matrix, int i, int j, int r, int c) {
        int idx;
        for(idx = j; idx <= c; idx++) {
            if(abs(matrix[i][idx]) <= 100) {
                res.push_back(matrix[i][idx]);   
            }
            matrix[i][idx] = 101;
        }

        for(idx = i+1; idx <= r; idx++) {
            if(abs(matrix[idx][c]) <= 100) {
                res.push_back(matrix[idx][c]);   
            }
            matrix[idx][c] = 101;
        }

        for(idx=c-1; idx >= j; idx--) {
            if(abs(matrix[r][idx]) <= 100) {
                res.push_back(matrix[r][idx]);   
            }
            matrix[r][idx] = 101;
        }

        for(idx=r-1; idx > i; idx--) {
            if(abs(matrix[idx][j]) <= 100) {
                res.push_back(matrix[idx][j]);   
            }
            matrix[idx][j] = 101;
        }
    }

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int r = m-1, c = n-1, i = 0, j = 0;

        vector<int> res;

        while(i <= r && j <= c) {
            traverse(res, matrix, i, j, r, c);
            i++; j++; r--; c--;
        }

        return res;
    }
};

Decoding the Code: Step-by-Step Breakdown

The code is divided into two main functions:

a) spiralOrder (Public Function):

Initialization:

It retrieves the matrix dimensions (m for rows, n for columns).
It initializes variables representing the boundaries (i, j, r, c) for the entire matrix (top-left and bottom-right corners).
It creates a result vector (res) to store the elements in spiral order

Looping Through Layers:

It employs a while loop that continues as long as both i (top row) is less than or equal to r (bottom row) and j (leftmost column) is less than or equal to c (rightmost column). This ensures the loop iterates until all elements within the matrix boundaries are processed.
Traverse a Layer: Inside the loop, it calls the helper function traverse with the current boundaries (i, j, r, c) and the result vector (res). This call essentially processes a single layer of the spiral within the specified boundaries.
Update Boundaries: After traversing a layer, the loop updates the boundaries (i, j, r, c) by incrementing i and j (moving inwards) and decrementing r and c (shrinking the remaining area). This effectively prepares the boundaries for the next layer of the spiral.

b) traverse (Helper Function):

Logic for Traversing a Single Layer: It takes the matrix (matrix), boundaries (i, j, r, c) representing the current layer's top-left and bottom-right corners, and the result vector (res) to store the elements in spiral order.(matrix[i][j] will be the starting element for 1 traverse)
Looping Through Elements: It uses four for loops, each iterating through an index (idx) to visit the elements in the current layer:

Move Right (First Row): The first loop iterates from j (leftmost column) to c (rightmost column) in the current row (i). It checks if the element matrix[i][idx] is unvisited (absolute value less than or equal to 100) using abs(matrix[i][idx]) <= 100. If unvisited, it adds the element to the res vector and marks it as visited by assigning a high value (101) to matrix[i][idx].
Move Down (Last Column): Similar to the first loop, this iteration goes from i+1 (the row below the first row) to r (bottommost row) in the current rightmost column (c). It follows the same logic of checking for unvisited elements and adding them to the result with a visit mark.
Move Left (Last Row): This loop iterates from c-1 (one column before the last) to j (leftmost column) in the bottom row (r). It checks and adds unvisited elements.
Move Up (First Column): The final loop iterates from r-1 (one row above the bottom row) to i-1 (1 row below the topmost row) in the current leftmost column (j). It uses the same logic for checking, adding, and marking visited elements.

Key Points:

The traverse function ensures that elements are visited only once by checking if their absolute value is less than or equal to 100 (since in the constraints it is mentioned that items of the matrix are in the range [-100, 100]). Marking visited elements with a high value (101) prevents revisiting them.
The spiralOrder function progressively shrinks the boundaries (i, j, r, c) as it processes each layer, effectively spiralling inwards until all elements are captured.

Testing the Code

Let’s delve into some test cases to solidify our understanding of how the provided C++ code accomplishes the spiral order traversal:

Test Case 1: Basic Spiral

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Expected output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Walkthrough:

Initialization:

The code retrieves the matrix dimensions (3 rows, 3 columns).
It sets boundaries (i = 0, j = 0, r = 2, c = 2).
An empty result vector (res) is created.

Looping Through Layers:

The while loop starts (i <= r and j <= c are true).
a) First Layer Traversal:

The traverse function is called with boundaries (i = 0, j = 0, r = 2, c = 2).
It iterates through the first row (elements 1, 2, 3) from left to right, adding them to res and marking them visited.
It moves down the rightmost column (element 6), adding it to res and marking it visited.
It iterates through the last row (elements 9, 8) from right to left, adding them to res and marking them visited.
It moves up the leftmost column (element 7), adding it to res and marking it visited.
After traversing the first layer, res becomes [1, 2, 3, 6, 9, 8].
Boundaries are updated (i = 1, j = 1, r = 1, c = 1).

b) Second Layer Traversal:

The loop iterates again (i <= r and j <= c are still true).
The traverse function is called with the updated boundaries.
It tries to iterate through the top row (element 4) but finds it already visited.
It moves down the rightmost column (no element present).
It tries to iterate through the bottom row (element 5) but finds it already visited.
It moves up the leftmost column (no element present).
Since no new elements were found, this layer traversal effectively ends.

c) Loop Termination:

After the second layer, i (now 1) is greater than r (now 1), and the while loop terminates.

Return Result:

The function returns the final res vector containing the spiral order traversal: [1, 2, 3, 6, 9, 8, 7, 4, 5].

Test Case 2: Rectangular Matrix

Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8]]
Expected Output: [1, 2, 3, 4, 8, 7, 6, 5]

Walkthrough:

This case follows similar logic to the first test case, but with fewer layers due to the rectangular shape. The code will traverse the elements in a spiral pattern, starting from the top-left corner and moving inwards until all elements are visited.

Real-World Applications: Beyond the Classroom

Image Processing: When dealing with digital images represented as matrices (pixels as elements), spiral order traversal can be used for efficient image compression techniques. By prioritizing central pixels that often contain crucial image information, this approach can achieve better compression ratios.
Data Mining: When analyzing large datasets represented as matrices, spiral order traversal can be used to prioritize processing central elements that might hold more valuable or statistically significant information compared to the edges.

These are just a few examples, and the specific applications can vary depending on the software and its purpose. However, the core concept of efficiently iterating through a matrix in a spiral pattern proves valuable in various real-world scenarios.

Conclusion

We’ve successfully navigated the challenge of finding the spiral order traversal in a matrix! This problem not only tested our understanding of matrix manipulation and loops but also introduced a valuable concept with practical applications. By combining clear explanations, code breakdown, and real-world examples, I have hopefully provided a comprehensive guide to tackling this spiral adventure.

Solving a Leetcode problem daily — Day 2: Plus One

Subhradeep Saha — Sat, 04 May 2024 18:30:00 +0000

Solving a Leetcode problem daily — Day 2: Plus One | by Subhradeep Saha | Medium

Subhradeep Saha ・ May 5, 2024 ・
Medium

Here is the Leetcode problem - Plus One

Problem Statement

Imagine you have a very large number stored as an array of digits, where each element in the array represents a single digit of the number. The digits are arranged in big-endian order, meaning the most significant digit (leftmost) is at index 0, and the least significant digit (rightmost) is at the last index. Additionally, there are no leading zeros in this number (according to the constraints).

The challenge is to write a function that takes this array of digits representing a large integer and increments the number by 1. The function should then return a new vector containing the digits of the incremented number.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

The input array (digits) will have a size between 1 and 100 (inclusive).
Each element (digits[i]) of the array will be a digit between 0 and 9 (inclusive).
There will be no leading zeros in the input array.

Understanding the Solution

Here’s a breakdown of the C++ code to solve this problem, explained line by line:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int idx = digits.size()-1;
        int carry = 1;

        while(idx >= 0) {
            int sum = digits[idx] + carry;
            if(sum < 10) {
                digits[idx] = sum;
                return digits;
            }
            digits[idx--] = sum % 10;
            carry = sum / 10;
        }

        if(idx == -1) {
            digits.insert(digits.begin(), carry);
        }
        return digits;
    }
};

Breakdown of the Code:

1. Function Definition:

class Solution {
public:
  vector<int> plusOne(vector<int>& digits) {

This function takes a reference to a vector of integers (digits) representing the large integer and returns a new vector containing the digits of the incremented number.

2. Initialization:

int idx = digits.size()-1;
int carry = 1;

We get the last index of the digits array and store it in idx. This will be used for iterating through the digits in reverse order.
We initialize a variable carry to 1, representing the increment value we want to add.

3. Carry-Over Logic:

while(idx >= 0) {
      int sum = digits[idx] + carry;
      if(sum < 10) {
        digits[idx] = sum;
        return digits;
      }
      digits[idx--] = sum % 10;
      carry = sum / 10;

}

Looping and Sum: We use a while loop to iterate through the digits array as long as idx is not negative (i.e., we haven't reached the beginning of the array). Inside the loop, we calculate the sum by adding the current digit (digits[idx]) and the carry.
Early Return (No Carry-Over): If the sum is less than 10, it means there's no carry-over needed. We update the current digit (digits[idx]) with the sum and directly return the modified digits vector.
Updating Digit and Carry-Over: If the sum is 10 or greater, it signifies a carry-over. We update the current digit (digits[idx]). We use the modulo operator (%) to extract the digit at the current position (sum % 10). This digit is placed back into the corresponding element of the digits array.
We calculate the carry-over value (sum / 10) using integer division. This value is stored in the carry variable for the next iteration.
We decrement idx to move to the previous digit in the next iteration.

4. Overflow Case:

if(idx == -1) {
      digits.insert(digits.begin(), carry);
}
return digits;

Overflow Check: If the loop finishes iterating without returning (meaning idx becomes -1), it signifies an overflow case. This happens when the original number is so large that incrementing it by 1 requires an extra digit at the beginning (most significant position).
Adding a New Digit: To handle this, we use the insert function of the vector class. We insert the carry value (which is 1 in this case) at the beginning (digits.begin()) of the digits vector. This effectively adds a new digit to the most significant position.

Test Cases
Let’s see how the code works with different input scenarios:

Test Case 1:

digits = [1,2,3]
Expected Output: [1,2,4]
Explanation: Adding 1 to 123 results in 124. The code iterates through the digits, updates them accordingly, and no overflow occurs.

Test Case 2:

digits = [9]
Expected Output: [1,0]
Explanation: Adding 1 to 9 results in 10. The code handles the carry-over, updates the digit to 0 in the original array, and no overflow occurs.

Test Case 3:

digits = [9,9]
Expected Output: [1,0,0]
Explanation: Adding 1 to 99 results in 100. The code handles the carry-over twice, updating digits to 0 and adding a new digit (1) at the beginning to accommodate the overflow.

Real life applications of the problem

The concept of incrementing large integers represented as arrays of digits has various applications in the software world, here are a few examples:

1. Financial Transactions:
In finance systems, large numbers representing money amounts are often stored as arrays of digits for efficiency. When processing transactions that involve adding or subtracting money, incrementing or decrementing these arrays becomes necessary.

2. Counters and Statistics:
Many applications use counters to track various events or metrics. These counters can be represented as arrays of digits, especially when dealing with very large numbers. Incrementing these counters involves manipulating the digits in the array.

3. Large Number Arithmetic:
Libraries or custom functions for performing arbitrary precision arithmetic (calculations with very large numbers) might use arrays of digits to represent the operands (numbers involved in the calculation). Incrementing a number in such a library would involve manipulating the digit array.

4. Big Data Processing:
In big data processing, large datasets may contain numerical values like timestamps, user IDs, or counts. These values can be stored efficiently in arrays of digits. When iterating through such data and needing to update specific values (e.g., incrementing a count), the concept of incrementing digit arrays becomes relevant.

5. Cryptography:
Some cryptographic algorithms involve manipulating large integers. While not directly incrementing, these algorithms might require adding or subtracting large numbers, which could be implemented using digit array manipulation techniques similar to this problem.

It’s important to note that in modern software development, libraries or frameworks often handle large number manipulation behind the scenes. However, understanding the underlying concepts, like incrementing digit arrays, can be valuable for low-level programming, performance optimizations, or simply for a deeper grasp of how computers handle large numbers.

Conclusion

This C++ code efficiently increments a large integer represented as an array of digits by handling carry-over logic and potential overflow situations. By understanding the code and the test cases, you can now tackle similar problems that involve digit manipulation and array operations. Feel free to experiment with different input scenarios and challenge yourself further!

Solving a Leetcode problem daily - Day 1 | Pascal’s Triangle

Subhradeep Saha — Sat, 04 May 2024 06:04:54 +0000

I have written this blog originally in Medium -

Solving a Leetcode problem daily — Day 1: Pascal’s Triangle | by Subhradeep Saha | Apr, 2024 | Medium

Subhradeep Saha ・ May 3, 2024 ・
Medium

Here is the Leetcode problem - Pascal's Triangle

What is Pascal’s Triangle?

Imagine a pyramid of numbers where each element is the sum of the two numbers directly above it. That’s Pascal’s Triangle! Here’s a look at the first few rows:

As you can see, the first row always starts with a 1, and each subsequent row is built by adding the elements above it.

The LeetCode Challenge

The LeetCode challenge asks us to write a function that takes an integer numRows and returns the first numRows rows of Pascal's Triangle.

Understanding the Solution

Complete Code:

class Solution {
public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res(numRows);
    for (int i = 0; i < numRows; i++) {
      for (int j = 0; j <= i; j++) {
        int left = (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0;
        int right = (i >= 1 && j < i) ? res[i - 1][j] : 0;
        int sum = (left == 0 && right == 0) ? 1 : left + right;
        res[i].push_ back(sum);
      }
    }
    return res;
  }
};

Here’s a breakdown of the C++ code into sections:

1. Class and Function Definition:

class Solution {
public:
  vector<vector<int>> generate(int numRows) {

This code defines a class Solution with a public function named generate. This function takes an integer numRows as input and is designed to return a 2D vector of integers representing Pascal's Triangle.

2. Result Initialization:

vector<vector<int>> res(numRows);

Here, we create a 2D vector named res. This vector will have numRows rows, and it will be used to store the generated Pascal's Triangle. We are not initializing the number of columns here since the items will be pushed dynamically inside of the loop.

3. Nested Loops for Iterating Through the Triangle:

for (int i = 0; i < numRows; i++) {
      for (int j = 0; j <= i; j++) {

We use two nested loops to iterate through each element of the resulting triangle. The outer loop (i) iterates through each row (0 to numRows-1). The inner loop (j) iterates through each element (0 to i) within the current row.

Explanation of the Loops:
These loops ensure we visit each element in the 2D vector exactly once. The outer loop (i) progresses row by row, while the inner loop (j) fills the elements within each row. Since Pascal's Triangle has a specific structure where elements rely on previous rows, this nested loop approach is ideal for building it efficiently.

Next Steps:

In the next section, we’ll delve into how the code calculates the value for each element in the triangle using these loops.

4. Calculating Element Values:

The core functionality of the code lies within the inner loop:

int left = (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0;
int right = (i >= 1 && j < i) ? res[i - 1][j] : 0;
int sum = (left == 0 && right == 0) ? 1 : left + right;
res[i].push_back(sum);

Understanding the Logic:
left and right Variables:

These variables represent the values needed to calculate the current element’s sum based on Pascal’s Triangle’s property.
left: This stores the value from the element directly above and one position to the left. The ternary expression (i >= 1 && j >= 1) ? res[i - 1][j - 1] : 0) checks if we're not in the first row (i=0) or the first element (j=0) of any row. If valid, it accesses the element in the previous row using res[i - 1][j - 1]. Otherwise, it sets left to 0 (since there's no element there).
right: This stores the value from the element directly above. The ternary expression (i >= 1 && j < i) ensures we're not in the first row and j is within the current row's boundary (not the last element). If valid, it accesses the element above using res[i - 1][j]. Otherwise, it sets right to 0.

sum Calculation:

The sum variable holds the final value for the current element (i, j).
The ternary expression (left == 0 && right == 0) ? 1 : left + right) calculates the sum. If both left and right are 0 (meaning we're at the first element of a row), we set sum to 1 (since the first element in each row is always 1). Otherwise, sum is calculated by adding left and right.

Adding the Value to the Result:
Finally, res[i].push_back(sum) adds the calculated sum to the current row (res[i]) of the result vector.

Key Takeaway:

This logic leverages dynamic programming. By using previously calculated values (left and right from the previous row), the code efficiently builds the triangle element by element.

Next Steps:

In the final section, we’ll see how this code works with different inputs and the complete solution.

Now that we’ve explored the code’s building blocks, let’s see how it works with different inputs and how the pieces fit together to form the complete solution.

Test Cases and Explanation

Let’s see the code in action with some test cases:

Test Case 1: numRows = 1

Output: [[1]]

Explanation:
The first row of Pascal’s Triangle always has a single 1, and the code correctly handles this case using the logic for the first element (left and right become 0, so sum is set to 1).

Test Case 2: numRows = 3

Output: [[1], [1, 1], [1, 2, 1]]

Explanation:

Row 1: We have only one element (1) as explained in Test Case 1.
Row 2: left for the first element (j=0) is 0 (since we're in the first column of row 2). right (element directly above) is also 0 (since we're in row 2). Therefore, sum becomes 1 (as both left and right are 0). This process repeats for the second element (j=1) in row 2, where left becomes 1 (referring to the first element in row 1) and right is still 0. So, sum is 1 + 0 = 1.
Row 3: The calculation for the first element (j=0) follows the same logic as row 2, resulting in sum as 1. For the second element (j=1), left is 1 (referring to the element above and to the left) and right is 1 (referring to the element directly above). So, sum is 1 + 1 = 2. The calculation for the third element (j=2) uses left as 1 and right as 1, resulting in sum as 1 + 1 = 2.

Conclusion

This code effectively generates Pascal’s Triangle in C++ by leveraging dynamic programming and nested loops. By understanding the logic behind calculating element values and the role of each code section, you can now tackle this LeetCode problem and similar problems that involve building upon previously calculated results.

Feel free to experiment with the code by changing the numRows value and observe how the triangle grows! Happy coding!

DEV Community: Subhradeep Saha

Solving a Leetcode problem daily — Day 12 | 347. Top K frequent elements

Solving a Leetcode problem daily — Day 12 | 347. Top K frequent elements | by Subhradeep Saha | May, 2024 | Dev Genius

Problem Statement

Constraints:

High Level Approach

Code Implementation in C++

Detailed Code Breakdown:

Frequency Counting:

Priority Queue with Custom Comparison:

Populating the Priority Queue:

Extracting Frequent Elements:

Returning the Result:

Code Dry Run with Test Case:

Frequency Counting:

Priority Queue Population:

Extracting Frequent Elements:

Time and Space Complexity Analysis

Time Complexity:

Space Complexity:

Real-World Applications

Conclusion

References

Solving a Leetcode problem daily — Day 11 | Find Minimum in Rotated Sorted Array

Solving a Leetcode problem daily — Day 11 | Find Minimum in Rotated Sorted Array | by Subhradeep Saha | May, 2024 | Dev Genius

Problem Statement

Constraints:

High-Level Approach

How are we getting the min element?

Now how to identity the max element?

How are we updating the l, h and why?

Code Implementation in C++

Detailed Breakdown of the Code:

findPeakIdx():

findMin():

Dry Run with a Test Case

InsidefindPeakIdx() :

InsidefindMin() :

Time and Space Complexity Analysis

Real-World Applications

Conclusion

References

What next?

Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array

Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 11, 2024 ・ Medium

Problem Statement

Constraints:

High-Level Approach

Binary search to the rescue

How are we finding the indices?

Code Implementation in C++

Breakdown of the Code

Dry Run with a Test Case

Searching for First Occurrence (firstIdxSearch = true):

Inside the main searchRange() function

Searching for Last Occurrence (firstIdxSearch = false):

Complexity Analysis

Possible Improvements in the code

Real-World Applications

Conclusion

References

What next?

Solving a Leetcode problem daily — Day 9 | First Bad Version

Solving a Leetcode problem daily — Day 9 | First Bad Version | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 9, 2024 ・ Medium

Problem Statement

Constraints:

High-Level Approach

Reduce calls by using some space?

Hint for Binary Search?

Code Implementation(in C++)

Breakdown of the Code

Binary Search Initialization:

Binary Search Loop:

Returning the Result:

Further improvements in the code

Dry Run with a Test Case

Time and Space Complexity Analysis

Conclusion

`findPeakIdx()`:

`findMin()`:

Inside`findPeakIdx()` :

Inside`findMin()` :

Subhradeep Saha ・ May 11, 2024 ・
Medium

Searching for Last Occurrence (`firstIdxSearch` = false):

Subhradeep Saha ・ May 9, 2024 ・
Medium

Subhradeep Saha ・ May 7, 2024 ・
Medium

Subhradeep Saha ・ May 4, 2024 ・
Medium

Subhradeep Saha ・ Apr 30, 2024 ・
Medium

Subhradeep Saha ・ May 6, 2024 ・
Medium

Subhradeep Saha ・ Apr 28, 2024 ・
Medium