DSA GRIND #2

DSA GRIND #2


by Ashur Baroutta

    This week I spent most of my free time trying to come up with a solution for a problem called 3Sum. The problem statement reads "Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] equals 0". 

    A far from easy task for me to accomplish. Given the problem statement pointed out we cant have duplicates return in the trips, the first thing I did was sort the array so it'd be easier to iterate through and account for duplicates. I then initialized a new Linked List data structure in order to store the triplets as an array in each node. At this point I started a for loop and set the exit condition to be the length of the array-2, this is because I'm going to be using the last index as a right hand pointer that we keep sliding over (last index in arrays is always length-1).

    After this I set up various conditions to check for edge cases and situations in which the three separate indexes equaled 0. Whenever I found a triplet that did equal 0 I added the triplet to the linked list then I looped and incremented my left/decremented my right pointer by 1 until they moved passed any duplicates and repeated the same process. It is important to note that when they didnt equal 0, I would check if they were less then 0, as if they were then left pointer would be incremented by 1 since decrementing the right pointer would only ever make the end result smaller (remember we sorted the array already so reducing the value when theyre already less than 0 is counter productive.)

The results are below, might not be the fastest solution given its O(N^2) time complexity and O(N) space complexity. I am still pleased regardless and am going to be trying different problems similar to this in the following weeks. 


Comments

  1. EricaSeptember 22, 2022 at 3:48 PM

    Very nice work again, Ashur. Tackling problems like these will undoubtedly help with understanding vs. memorization-- and will help you be more versatile. Looking forward to the next one!

    ReplyDelete

Post a Comment

Popular posts from this blog

IP #6 : Reversing an Integer

Image
 Reversing an Integer by Ashur Baroutta     The focus of this submission will be on reversing a given integer passed into our function. Our problem statement is as follows "Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 -1], then return 0." Seems simple, though was actually a little odd. My initial reaction is to convert the integer to a string and then just reverse each character. Though in a way that feels like cheating as I don't think that solution is in the spirit of the assignment,  and it takes more resources to complete.      Pivoting my attention to a mathematical solution made the problem a lot more fun. Say our first example for x is 123. The way we attack it is to setup variables to track the reversed total and to track the remainder of a given iteration, we also create a loop iterating through while x does not equal 0.  The ...
Read more

IP#5 : LinkedList Removing Duplicates II

Image
 Removing Duplicates II by Ashur Baroutta         In our last submissions, we worked on removing duplicates, this week we look at the more complicated problem of the same type. Our problem statement is " Given the  head  of a sorted linked list,  delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list . Return  the linked list  sorted  as well ."      So not only do we have to remove duplicates, but we cannot return values that are not distinct, for example, if our list originally contained three 1's, we need to delete all the 1's in our list as even if we delete all but one of them, the number 1 itself is not a distinct value.      This took me about 3 days to think through and complete, the following is our code submission.  We start by first creating a new ListNode called newlist. We set its .next reference pointing to head (the ListNode passed ini...
Read more