DSA GRIND #1

by Ashur Baroutta

    The first submission of the new semester will be focusing on the continuation of my data structure and algorithms training. I will be trying to push my limits each week and attacking several more problems to keep different methods/thought processes of problem solving sharp in my mind.

Problem #1 : Remove Duplicates From Sorted Array

Problem Statement : 

    "Given an integer array *nums* , sorted in non decreasing order, remove duplicates inplace such that unique elements appear only once, the order of the elements should be kept the same. After this, return k, where k is the number of unique elements remaining in the array. Do not allocate extra space for another array, this must be done by modifying the input array in place with O(1) extra memory (constant space complexity). "

Solution : 

    I start by covering the edge cases with an if statement, if the length of the input array is 1 or 0, simple return the length of the array as that is the number of unique elements remaining in the array. I then initialized a variable to maintain an index of unique elements ( j ). From there I implemented a for loop and with each iteration through the elements, i checked if the current element is not equal to the next element, as if they were not equal I set the element of index j++ ( it is important to note in java the number is read and only after being read incremented by one, when in the format j++) equal to the element of index i, this acted like a current state variable and a counter (because j is being incremented!). I am more than happy with the results, tying top speeds of all submissions and managing space as requested by the problem statement. The submission stats are shown in the image below. 

Problem #2 : Shuffle the Array 

Problem Statement : 

    "Given the array *nums* consisting of 2n elements in the form [x1,x2,....,y1,y2]

return the array in the form [x1,y1,x2,y2,.....,xn,yn]"

Solution : 

    I start by initializing three variables ( i , j , mid) where i, j = 0 and mid = n. Then I make a new integer array to store the results. After this I make a while loop that breaks only when i > n, as we're not needing to make swaps after the n'th element. So with each loop we set the new array's, ans, index of j++ equal to the input arrays, nums, index of i++. Immediately after we set again ans[j++] equal to nums[mid++]. Why did we do this? The first equal was to keep our x in the same place, incrementing index's by one brings us to the y's place and then the second equal completes the swap for our y's! As mid's value is n, we know n starts where our y of n begins! So we increment the same way ans[j++] = nums[mid++]. This is why its important we noted how the incrementation and reading of the variable works in java. 

To help you better understand, say our input was an array nums = [2,5,1,3,4,7], n = 3.

We know, given how the problem statement reads, the first elements until n are our x values with ascending index. So remember our first iteration i and j are 0. When we set ans[j++] = nums[i++] we are saying the 0th index is going to remain the same, effectively making our i represent each x element. Only then after are i and j incremented to 1. Immediately following that statement we set ans[j++] = nums[mid++], see here j is being read as 1, meaning the element following our x has been set equal to the first y element and mid is acting as our y tracker as its initial placement was at the first y index. Now both j and mid have been incremented, and the cycle repeats effectively swapping until each x and y are in their appropriately place. The submission results shown below.

Apologies if the explanation was a bit much, but I find myself forgetting things as I encounter problems that are similar but still different in specific ways. I feel the more in-depth I go at explaining how each line works I develop a more concrete understanding of my work. I've also started keeping a notebook explaining all my solutions to myself as well for reference if I should ever run into something vaguely similar.