## Posts

Showing posts from June, 2021

### Merge k Sorted Lists Solution - The Coding Shala

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 val; * ListNode next; *

### How to Find the Length of a Linked List using Recursion - The Coding Shala

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 ; } re

### LeetCode - Check if Word Equals Summation of Two Words Solution - The Coding Shala

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

### First Missing Positive Solution - The Coding Shala

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 is av

### Find First and Last Position of Element in Sorted Array Solution - The Coding Shala

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 ) { int [] result

### 3Sum Problem Solution - The Coding Shala

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 the s