yswnth

Never have a zero day. One set at the gym counts. One paragraph written counts. The bar is deliberately, almost ridiculously low. The only way to fail is to do literally nothing.

Okay, this is mainly regarding today’s DSA placement session. Okay, I have completed around two questions from Striver’s A2Z Sheet. Two hard problems: first one is 3Sum from the array, and second one is 4Sum from the array. Within these two problems, usually there will be three kinds of solutions, right? Brute, better, and optimal. For both of them, what I tried to solve is all three solutions. Let’s start with the first problem, 3Sum. The problem statement says that we need to find a set of three elements such that it sums up to a specific target. The target will be given and the array will be given. What we need to provide as output is a set of triplets. That’s the problem statement. Initially, the brute-force solution is very simple. We try to generate all sets of three numbers and check if the summation matches the target. If yes, just sort the order and add it to a set. We use a set data structure for this because we don’t want duplicates. It’s also mentioned in the constraints of the problem statement that we shouldn’t output duplicates. Yeah, this is the brute-force solution. The better solution is to use hashing. What we try to do is, let’s consider this as K, right? We know that: K = target - (I + J) That’s the logic we are going to use. What we really do is use just two loops, and for the third one, instead of a loop, we’ll just check with a hash set if the required value is already present. If it is present, then the target condition is satisfied and we’ll just add it to the output set. That’s the main workflow. Now going towards the optimal solution. The optimal solution uses pointers. I, J, and K are used here. I is used as a constant, and J and K are used as pointers. This can be done using the two-pointer method. What we try to do is fix the I value, and we’ll consider a sorted array instead of a normal array. Then what happens is we’ll check the remaining summation of J and K and compare it with the actual target. If it’s less than the target, we’ll move J forward because the value has to increase, right? That’s the main concept. If the obtained value is greater than the target, then we need to decrease the value, so we’ll move K from the back side. That’s the main objective. The looping condition for this one is J < K. That’s the main condition because we need to check the whole range. If J and K cross each other, then the loop should end. That’s the main point of the optimal solution. Yeah, this is for it. For the next problem, 4Sum. It’s quite simple. It’s very similar to what we did with the 3Sum problem. For the brute-force solution, it’s directly related to the previous problem. Just generate all four elements and calculate their sum. If it equals the target, then append it to the set after sorting so there will be no duplicates. The better solution is to use hashing itself, but we’ll consider one extra loop because of the extra element involved. That’s how we directly solve this problem. We’ll just have the loops and then apply the hashing logic. For the optimal solution, it’s very similar to what we had done in the previous problem. We’ll consider I, J, K, and L. Within this, we’ll try to keep I and J through loops, and K and L act as pointers. Same previous logic: If the summation is less than the target, then we’ll move K forward. If it’s greater than the target, then we’ll decrease the L index. One more thing is that: I starts at 0, J starts at I + 1, K starts at J + 1, and L starts at the last index, which means N - 1. Yeah, that’s the logic. This is the optimal approach to solve this problem. For today, I have done only two problems. Yeah, this is it for today. Let’s see if I can rock more tomorrow. I think Largest Subarray with Sum Zero maybe I’ll be solving tomorrow. Yeah.