Coding Essentials 102

Hi there! This is Aman again. This time I’ve come up with a very frequent problem asked in coding interviews as well as coding competitions. This problem looks very easy on the surface and we immediately understand it. But it becomes cumbersome to think how it would be solved.

My experience has been that I’ve been just trying to solve the problem in just one fragment which ultimately backfires any ability to check for all cases.

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Input: nums = [1,2,3,4,5,6,7], 
k = 3 
Output: [5,6,7,1,2,3,4]

Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6]
 rotate 2 steps to the right: [6,7,1,2,3,4,5]
 rotate 3 steps to the right: [5,6,7,1,2,3,4]

Looking a the problem we can figure out how to solve it. But what I was trying to do was this:

rotateArray(List<int> I, int n){
  List<int> temp = List.empty(growable:true);

    if(n <= I.length){
      for(int i= ((I.length - 1)-(n-1)); i< I.length; i++){
      temp.add(I[i]);
    }
  
    for(int i=0; i< ((I.length - 1)-(n-1)); i++){
      temp.add(I[i]);
    }
    }
  else{
    print("cannot compute");
  }
  
  return temp;
}

I was checking from i= (length-1)-(frequency-1) as a tightly coupled condition to check the array. Although this soultions was working but not conforming to the Input constraints.

For example, frequency is no dependent on Input array’s length that means (n<0<1000). My solution in this case would give range error and I won’t be able to satisfy all conditions.

That is where while loop comes to rescue, so that we fulfill all cases and also rather than using this messy logic we can simplify it using while loop and step by step iterative approach by simplifying solution to small solution sets.

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        int n = nums.length;
        reverseNum(nums,0,n-1);
        reverseNum(nums,0,k-1);
        reverseNum(nums,k,n-1);
    }
    public void reverseNum(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Here, I’m basically manipulating my array step-by-step rather than manipulating it at once, also the while loop does the iterations on any k values without depending on array’s length.

Notice that I haven’t given any tightly coupled constraint to them so it’s easy to go through and manipulate arrays. For example

Given an array = [1,2,3,4,5]
K(frequency) = 2;
n = nums.length;

Beacuse we can get any frequency,no matterhow muchfrequency weget whateverthe modulusif itwill comeback, sowe will alwayscxalulate kusing

k=k%nums.length;

Now we call our reverseNum function which will step by step manipulate our array.

public void reverseNum(int[]nums,int start,int end){
  while(start < end){
    int temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        int n = nums.length;
        reverseNum(nums,0,n-1);
        reverseNum(nums,0,k-1);
        reverseNum(nums,k,n-1);
    }
    public void reverseNum(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}