Week 1 updates

We all know the feeling: there’s something we should be doing, but we keep pushing it aside—whether it’s a task we dread or something we’re simply avoiding. For me, this was learning DSA. I had the resources, I knew the importance of it, but procrastination kept holding me back. I would tell myself, "I'll start tomorrow," but tomorrow never seemed to come.

Then, I stumbled upon a video by Savinder Puri, which completely shifted my perspective. In it, he talked about the importance of public commitment—putting your goals out there so that you feel a sense of responsibility to follow through. That video inspired me to commit publicly on LinkedIn that I would learn DSA and document my progress.

From that moment on, I made a promise to myself to put in the work, and I’m proud to say that I’m sticking to it. This week, I focused on arrays and bit manipulation, and the journey has been incredibly rewarding. Here’s a look at what I learned and how I’ve been applying these concepts.

Bit Manipulation: A Surprising Discovery

Before this week, I had never really delved into bit manipulation. I’d always thought of it as one of those topics not often asked in coding interviews, so I didn’t pay it much attention. But as I started exploring it, I quickly realized I was wrong—bit manipulation is an essential tool in a programmer's toolbox, and the learning curve is much easier than I initially thought once you get the basics down.

I was particularly surprised by how bit manipulation can simplify problem-solving. When I needed to find the element with an odd occurrence in an unsorted array, I discovered that the XOR gate makes it surprisingly easy. It allowed me to get the result without needing extra space, unlike methods that require sorting or using a hashmap. This technique also worked when I had to find two odd-occurring elements in an unsorted array. The key difference was isolating the rightmost set bit to divide the elements into two groups, helping me identify each element efficiently. The XOR gate has become my go-to tool whenever I need to find odd occurrences or duplicates in an array.

Right shift and left shift operations are really useful for determining the length of consecutive 1’s in an integer or checking if a number is sparse (i.e., having two consecutive set bits). These operations help remove the trailing set bits, which simplifies the task.

While solving the problem of whether a number is a power of 2, I came across a fact that should've clicked sooner: if a number is a power of 2, its AND with the number just less than it will be 0. It was such a simple yet powerful fact—I should've known this, especially as an electronics engineering student! 😅

When working on counting the set bits in a number, I came across Brian’s Algorithm (Subtracting 1 from a decimal number flips all the bits after the rightmost set bit including the rightmost set bit), which helped me reduce the time complexity to O(number of set bits). This algorithm works by using the number and performing an AND with the number just less than it, eliminating one set bit at a time (the same approach I found while solving if a number is a power of 2).

def countsetbits(n):
    res=0
    while n:
        n=n&(n-1) #This line uses the brian algorithm
        res+=1
    return res

I never knew we could have an iterative solution for generating powersets using bit manipulation. The idea is simple: assign one bit to each element of the set, and then loop through all possible combinations by running a loop from 0 to 2^n −1, where N is the number of elements. Each bit pattern corresponds to a subset of the set, and you can easily extract the elements based on which bits are set.

Bit manipulation can make some DSA problems easier!

PS: I still sometimes get confused about which one out of these << and >> is the left-shift operator. 😅

Before learning about the shifting operators, whenever I saw log(n) as the expected time complexity, my first thought was to use divide and conquer, but from now on, I will also think about shifting operators.

While I’ve made good progress with basic bit manipulation techniques, I still need to explore more advanced bitwise operations and their applications in complex algorithms like bit masking.

After learning how bit manipulation can simplify problem-solving, I moved on to another fundamental topic: arrays.

---

Arrays: The Topic Everyone Hopes Their Interviewer Will Ask About in Technical Interviews

Arrays—one of the simplest topics in data structures—can become a bit more challenging when you start solving medium and hard-level questions.

When I was tackling the Longest Even-Odd Subarray, I initially tried solving it using two nested loops. However, I soon realized that by starting the loop from the second element (considering 0-based indexing), I could reduce the time complexity from O(n²) to O(n). This small adjustment made a big difference in performance.

Next, I encountered the Majority Element problem, which led me to Moore’s Voting Algorithm. The idea behind this algorithm is simple: if an element occurs more than n/2 times, it’s the majority element. Moore’s algorithm leverages this by keeping a candidate element and adjusting the vote count—if the element matches the candidate, the vote is incremented; if not, it’s decremented. When the vote count reaches zero, a new candidate is considered.

Last week, I realized that I had unknowingly been using the Sliding Window Technique in a few problems—finally got to know the formal name for it!

While solving the Minimum Flips problem, I came across an interesting observation: the number of groups of 0’s and 1’s would either be equal, or their difference would be just 1. This means you can always flip the second group because it will either have the same count or fewer elements than the first group. It was a surprising realization for me!

The problem that taught me a lot (I swear) how to traverse arrays circularly was the Maximum Circular Subarray Sum. I struggled with it at first, but then I got help. One way to solve it was by using two nested loops (i, j), where the jth loop runs from 1 to n—not from i + 1. The key here was calculating the index of each element as (i + j) % n, which made it easy to compute the circular sum of the subarray.

However, there’s an even simpler way to approach this problem using Kadane’s Algorithm.

def kadane(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Kadane’s algorithm helps find the maximum sum of a subarray in O(n) time. To solve the circular subarray problem, we can combine Kadane's algorithm with the concept of the minimum sum subarray. If we can find the Minimum Sum of a Subarray, we can determine the Maximum Sum by subtracting the minimum sum from the total sum of the array. This approach not only simplifies the understanding but also reduces the time complexity to O(n).

So, the steps are:

1. Find the maximum sum using Kadane’s algorithm (for non-circular subarrays).

2. Calculate the total sum of the array and find the minimum sum subarray using Kadane's algorithm for the negative elements.

3. The maximum circular sum is then the total sum minus the minimum sum.

By using this approach, you avoid the nested loop solution, reducing the complexity and making the problem much more efficient to solve.

Conclusion

In conclusion, this week’s dive into bit manipulation and arrays has been both enlightening and challenging. I’ve learned powerful techniques like Moore’s Voting Algorithm and Kadane’s Algorithm, tackled complex problems, and gained a better understanding of time complexity optimization. While there’s much more to explore, I’m excited to continue my learning journey and share my progress with you all.

If you are curious about what problems have I solved then here’s a list for you:

• PowerSets using Bitwise

• Two Odd Occurring Elements

• Power of 2

• Swap All Odd and Even Bits

• The number is Sparse or Not

• Gray to Binary Equivalent

• Binary to Gray Code Equivalent

• Longest Consecutive 1s

• Count Set Bits

• Sliding Window Technique

• Minimum Flips to Make Binary String Alternating

• Majority Element

• Subarray with Given Sum

• Maximum Circular Subarray Sum

• Longest Even Odd Subarray

• Max Subarray Sum