The Coding Shala

Home >> Data Structures >> Linked List Introduction and its Implementation  In this post, we will learn what is linked list data structure and will implement a singly linked list in Java. Linked List Data Structure A linked list is a linear data structure. The linked list is a chain of Nodes that are connected using pointers. One Node contains the data/element and a pointer called next that points to the next node. Unlike arrays, linked list elements are not stored in a contiguous location. There are different types of the linked lists like a singly linked list, doubly linked list, and circular linked list. Here we will cover a singly linked list. The following are main terms used in a linked list: head: front node of a linked list next: pointer to the next node node: contains data/value and the next pointer We can create a linked list of different data types like integer, string, etc. Advantages and Disadvantages of linked lists The following are some advan...

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 >> Data Structures >> Find the Length of a Linked List using Recursion  In this post, we will learn how to find the length of a linked list using recursion in Java. How to Find the Length of a Linked List using Recursion You have given a singly linked list, write a Java program to count the number of elements or length of the linked list using recursion. Example 1: LinkedList: 1->2->3->4->5 Output: 5 Example 2: LinkedList: 2->4->6->7->5->1->0 Output: 7 Approach 1 If the current node is null then it will be our break condition of recursion. Java Program:  /* class Node{ int data; Node next; Node(int a){ data = a; next = null; } }*/ class Solution { public static int getCount ( Node head ) { return findLength ( head ); } public static int findLength ( Node curr ) { if ( curr == null ) { return 0 ; } ...

Home >> Data Structures >> Find the Length of a Linked List  In this post, we will learn how to find the length of a given linked list in Java. How to Find the Length of a Linked List You have given a singly linked list, write a Java program to count the number of elements or length of the linked list. Example 1: LinkedList: 1->2->3->4->5 Output: 5 Example 2: LinkedList: 2->4->6->7->5->1->0 Output: 7 Approach 1 Traverse the linked list until you reached the null node. Java Program:  /* class Node{ int data; Node next; Node(int a){ data = a; next = null; } }*/ class Solution { public static int getCount ( Node head ) { int count = 0 ; Node curr = head ; while ( curr != null ) { count ++; curr = curr . next ; } return count ; } } Other Posts You May Like Design Linked List...

Home >> LeetCode >> Check if Word Equals Summation of Two Words  In this post, we will learn how to solve LeetCode's Check if Word Equals Summation of Two Words problem and will implement its solution in Java. Check if Word Equals Summation of Two Words Problem The letter value of a letter is its position in the alphabet starting from 0 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, etc.). The numerical value of some string of lowercase English letters s is the concatenation of the letter values of each letter in s, which is then converted into an integer.  For example, if s = "acb", we concatenate each letter's letter value, resulting in "021". After converting it, we get 21. You are given three strings firstWord, secondWord, and targetWord, each consisting of lowercase English letters 'a' through 'j' inclusive. Return true if the summation of the numerical values of firstWord and secondWord equals t...

Home >> Interview Prep >> First missing positive  In this post, we will learn how to solve the First Missing Positive problem and will implement its solution in Java. First Missing Positive Problem Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space. Example 1: Input: nums = [1,2,0] Output: 3 Example 2: Input: nums = [3,4,-1,1] Output: 2 First Missing Positive Java Solution Approach 1 Time Complexity: O(n) Space Complexity: O(1) The steps are below to solve this problem: Step 1: The first missing positive number will be in the range of 1 to N+1, where N is the length of the array. So Other than these numbers we can ignore, make this change in the array. Step 2: Now we will take the array elements as the index(their original position), and at the numbers' original position will make the array element negative so later we can check this number ...

Home >> Interview Prep >> Find first and the last position of an element in a sorted array  In this post, we will learn how to Find the First and Last Position of Element in Sorted Array and will implement its solution in Java. Find First And Last Position of Element in Sorted Array Problem Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1] You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Example 3: Input: nums = [], target = 0 Output: [-1,-1] Find First and Last Position of Element in Sorted Array Java Solution Approach 1 Using Binary Search. Time complexity: O(log n) Java Program:  class Solution { public int [] searchRange ( int [] nums , int target ) { ...

Home >> Interview Prep >> 3Sum Problem  In this post, we will learn how to solve the 3Sum Problem and will implement its solution in Java. 3Sum Problem Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicates. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Example 2: Input: nums = [] Output: [] 3Sum Java Solution Approach 1 We can solve this problem using brute force but time complexity will go O(n^3) in that case. The brute force solution can be improved using Two pointer technique and the time complexity will be O(n^2). The steps are below for that: Step 1. First, sort the array so we can use two pointer technique to figure out which side we need to move our pointer. Step 2. Now we can solve this like 2 Sum problem. To remove the duplicate pairs we need to check if two continuous elements are t...