The Coding Shala

Home >> Interview Prep >> Find the middle element in a linked list  In this post, we will learn how to find the middle element in a linked list and will implement its solution in Java. Find a middle element in a linked list Problem Given a singly linked list of N nodes. The task is to find the middle of the linked list. Example 1: Input: LinkedList: 1->2->3->4->5 Output: 3  Explanation:  Middle of linked list is 3. Example 2:  Input: LinkedList: 2->4->6->7->5->1 Output: 7  Explanation:  Middle of linked list is 7. Find a middle element in a linked list Java Solution Approach 1 You can find the total length of the linked list then traverse again from starting and return the middle element. A better approach is to take two pointers one is a slow pointer, move by one step, and one fast pointer, move by two steps. At the time the fast pointer reaches the end slow is at the middle node. Java Program:  /* No...

Home >> Interview Prep >> Merge k Sorted Lists  In this post, we will learn how to solve the Merge k Sorted Lists problem and will implement its solution in Java. Merge k Sorted Lists Problem You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [   1->4->5,   1->3->4,   2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Merge k Sorted Lists Solution Approach 1 We can use an additional array to store all the elements from lists and then will sort this array. From the sorted array, we can make the linked list again. Time Complexity: O(n logn) Space Complexity: O(N) Java Program:  /** * Definition for singly-linked list. * public class ListNode { * int v...

Home >> Interview Prep >> Remove Duplicates from Sorted Linked List  In this post, we will learn how to Remove Duplicates from Sorted Linked List in Java. Remove Duplicates from Sorted Linked List Problem Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Remove Duplicates from Sorted Linked List Java Solution Approach 1 Iterative method. Time Complexity: O(n) Space Complexity: O(1) Java Program:  /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates ( ListNode head ) { if ( head =...

Home >> Interview Prep >> Majority Element  In this post, we will learn how to find Majority Element in the array and will implement its solution in Java. Majority Element Problem Given the array nums of size n, return the majority element. The majority element is the element that appears more than n / 2 times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Majority Element Java Solution Approach 1 First sort the array then find the frequency of elements, if the count is greater than n/2 return that. Time Complexity: O(nlogn)  [sorting] We can use HashMap to store the counts of elements that will take additional O(n) space. Java Program:  class Solution { public int majorityElement ( int [] nums ) { int check = nums . length / 2 ; Arrays . sort ( nums ); int count = 1 ; for ( int...

Last Updated: 20-Jan-2021 Home >> Interview Questions >> Count Number of Inversions in an array  In this post, we will how to Count the number of Inversions in an array and will implement its solution in Java. Count number of Inversions in an array Given an array A, count the number of inversions in the array. Inversion means how far the array is from being sorted. Formally speaking, two elements A[i] and A[j] from an inversion if A[i]> A[j] and i<j. Example: A : [2, 4, 1, 3, 5] Output : 3 Inversions are (2, 1), (4, 1), (4, 3). Count number of Inversions in an array Java Program Before solving this problem we need to understand what we need to do here. Here we need to count the number of inversions in an array. Inversions mean how far the given array is being sorted which means two elements A[i] and A[j] forms an inversion if A[i]>A[j] and i<j. To sort the array we need to swap these A[i] and A[j] and we count this as one inversion. We need to ...