Forem: Sumaiya Meem

Leetcode problem#876: Middle of the Linked List

Sumaiya Meem — Mon, 28 Nov 2022 08:29:45 +0000

Problem

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2:
Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

We solve this problem by using two pointers. We move the slow pointer by one step and the fast pointer by two steps. When the fast pointer is at the end of the Linked List after traversing, the slow pointer will be in the middle of the list.

Approach

Initially both pointers point to the first node (Head) of the Linked List.

Move slow pointer by one step and fast pointer by two steps.

Repeat the previous step.

There are odd numbers of nodes in the first example. In this case, the fast pointer can't move when the fast pointer.next = null. So, we return the slow pointer, which is the middle element of the Linked List.

And in the second example, there are even numbers of nodes. When the fastPointer = null, it returns the slow pointer, which is the second middle element of the Linked List.

Implementation (Java)

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fastPointer = head;
        ListNode slowPointer = head;

        while(fastPointer!= null && fastPointer.next!= null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        }
        return slowPointer;
    }
}

Complexity Analysis

Time complexity : O(n)
The list has been iterated n times where n is the length of the Linked List.

Space complexity: O(1)
No extra space has been used here.

Leetcode problem#217: Contains Duplicate

Sumaiya Meem — Fri, 25 Nov 2022 19:17:37 +0000

Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example:
Input: nums = [1,2,3,1] Output: true

Input: nums = [1,2,3,4] Output: false

Sorting

We can solve this problem by sorting the array. Time complexity for sorting is O(nlogn). After sorting, we loop through the array and match the consecutive numbers to find the duplicate values.

Implementation (Java)

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int pointer = 0;
        Arrays.sort(nums);

        while(pointer < nums.length-1){
            if(nums[pointer] == nums[pointer+1]){
                return true;
            }
            pointer++;
        }
       return false;
    }
}

However, this approach has a time complexity of O(nlogn). So we can follow a better way by using HashSet to optimize the time complexity.

HashSet

Java HashSet class implements the Set interface. It stores the elements in the hashtable and only holds the distinct values. For checking duplicate numbers, we can use contains() method.

Implementation (Java)

class Solution {
    public boolean containsDuplicate(int[] nums) {

        int pointer = 0;

        Set<Integer>checkNum = new HashSet<>();

        while(pointer < nums.length){
            if(checkNum.contains(nums[pointer])){
                return true;
            }
            checkNum.add(nums[pointer]);
            pointer++;
        }
        return false;
    }
}

Here we get the time complexity of O(n).

Leetcode Problem#283: Move Zeros

Sumaiya Meem — Wed, 23 Nov 2022 20:45:32 +0000

Problem
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

There are many ways to solve this problem. Here I am going to discuss about the optimal solution to tackle the challenge.

Using two pointers approach, we can solve this problem. Pointer One will look for non-zero elements and Pointer Two will swap the elements with Pointer One. We initialize both pointers to 0. Eventually all zero elements will be moved to the end.

Implementation (Java)

class Solution {
    public void moveZeroes(int[] nums) {

        int pointer=0;
        int n= nums.length;

        for(int i = 0; i < n; i++){
            if(nums[i]!= 0){
                int temp = nums[i];
                nums[i] = nums[pointer];
                nums[pointer] = temp;
                pointer++;
            }
        }
    }
}

Implementation (PHP)

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function moveZeroes(&$nums) {
        $pointer = 0;
        $numsLength = count($nums);

        for($i=0; $i<$numsLength; $i++){
            if($nums[$i]!=0){
                $temp = $nums[$i];
                $nums[$i]= $nums[$pointer];
                $nums[$pointer] = $temp;
                $pointer++;
            }
        }
    }
}

Solution Analysis

Time complexity = O(n)
Space complexity = O(1)

Note

Why are we not using Brute Force approach?

Through this approach, we traverse the whole array to find non-zero elements and store them in the starting indexes. And then we fill up the extra spaces with zero. Therefore, we get time complexity in the worst case.

Time Complexity = Time Complexity of filling non-zero elements + Time Complexity of filling zero elements = O(n)+O(n)= O(n)

Space Complexity = O(n) for extra space