Skip to content

#1 Arrays

Its a collection of similar items stored in contiguous memory locations.

It has 3 operations Insert, Delete, Search.

Using 2 pointers to resolve a problem: problems like given a sorted array ([-4,-1,0,3,10]), find the squares of that array arranged in sorted order.

for example, one approach for this problem would be to square the number O(n) and then sort it using nested for loop resulting in O(n^2) time which is time-consuming.

Let’s think about the 2 pointers solution with O(N) time we know that the array is sorted and it can also have -ve values so there is a chance that the min value could be the midpoint or first element. So let’s have one pointer at the start and another pointer at the end. Check if the Math absolute of the first element is greater than the last element if so add that at the new arrays the last element.

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] a = new int[nums.length];
        int i=0, j =nums.length-1, k=nums.length-1;
        while(i<=j)
        {
            if(Math.abs(nums[i])<Math.abs(nums[j]))
            {
                a[k] = nums[j]*nums[j];
                k--;
                j--;
            }
            else
            {
                a[k] = nums[i]*nums[i];
                k--;
                i++;
            }
        }
        
        return a;
    }
}

Insert

inserting can be done at the end, at the first resulting in shifting all the elements to the right or at the center with shifting

// First, we will have to create space for a new element.
// We do that by shifting each element one index to the right.
// This will firstly move the element at index 3, then 2, then 1, then finally 0.
// We need to go backwards to avoid overwriting any elements.
for (int i = 3; i >= 0; i--) {
    intArray[i + 1] = intArray[i];
}

// Now that we have created space for the new element,
// we can insert it at the beginning.
intArray[0] = 20;

Remove

deletion can be done at the end, at the first resulting in shifting all the elements to the left or at the center with shifting.

// Starting at index 1, we shift each element one position
// to the left.
for (int i = 1; i < length; i++) {
    // Shift each element one position to the left
    int_array[i - 1] = int_array[i];
}

// Note that it's important to reduce the length of the array by 1.
// Otherwise, we'll lose the consistency of the size. This length
// variable is the only thing controlling where new elements might
// get added.
length--;

Published inData Structures

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *