Code Katha

In this blog, we will discuss the "Product of Array Except Self" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution. Contents [ hide ] Problem Statement with Example Given an integer array nums , the task is to return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i] . The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. Let's consider an example to understand the problem: Example 1: Input: nums = [1, 2, 3, 4] Output: [24, 12, 8, 6] Explanation: The product of all elements except the element at index 0 is 2*3*4 = 24 ....

In this blog, we will discuss the "Contains Duplicate" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution. Contents [ hide ] Problem Statement 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. Examples Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Constraints 1 <= nums.length <= 10 5 -10 9 <= nums[i] <= 10 9 Practice: Leetcode Link Brute Force Solution Algorithm The simplest way to solve this problem is by comparing each element with every other element in the array. If any two ...

In this blog, we will discuss the "Best Time to Buy and Sell Stock" problem, which is a popular problem in coding interviews. We will go through the problem statement, explain the approach, and provide both brute force and optimal solutions. Additionally, we will perform a dry run of the code for better understanding and analyze the time and space complexity of each solution. Contents [ hide ] Problem Statement You are given an array `prices` where `prices[i]` is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you m...

The Array Two Sum Problem is a classic problem in computer science and programming. It is often asked in coding interviews and serves as a good exercise for beginners to learn about arrays, loops, and hash maps. In this blog, we will explore the problem statement, understand different approaches to solve it, and analyze the time and space complexity of each solution. Contents [ hide ] Problem Statement Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution , and you may not use the same element twice . Example 1: Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [5, 3, 1, 7, 8], target = 10 Output: [1, 3] Explanation: Because nums[1] + nums[3] == 10, we return [1, 3]. Practice: Leetcode Link Brute Force Solution The brute force ...

Understanding Arrays through a Story What is an Array? In the bustling town of Mysore, there was a famous grocery shop owned by Mr. Verma. Mr. Verma was known for his perfect organization. One day, he decided to teach his young apprentice, Shanav, the secret of his well-organized shop. Mr. Verma explained to Shanav that an array is like a special shelf where you can store multiple items of the same type in an organized manner. Think of it as a line of baskets, where each basket can hold one item. In Java, arrays are used to store multiple values in a single variable, instead of declaring separate variables for each value. Contents [ hide ] How to Declare an Array To create an array in Java, you need to specify the type of data it will hold and the number of elements it can store. Here’s how you do it: package codeKatha; public class GroceryShop { public static void main(String[] args) { int[] vegetablePrices = new int[5]; } } This line creates an array...

Welcome to this in-depth guide on the concept of graphs in computer science. Whether you're a complete novice or an advanced learner looking to refine your understanding, this tutorial will guide you through the core concepts, representations, and practical applications of graphs, ensuring a robust understanding of this fundamental concept. Contents [ hide ] Introduction to Graphs A graph is a data structure that consists of a set of nodes (also called vertices) and a set of edges that connect these nodes. Graphs are used to represent pairwise relationships between objects. In a graph, nodes can represent any type of entities such as people, cities, web pages, or even abstract concepts, while edges represent the relationships or connections between these entities. Graphs are used to model a wide variety of real-world situations, from social networks (like Facebook, LinkedIn) to computer networks (like the internet), from biological systems (like protein-protein i...

Welcome to our beginner's guide to Kruskal's Algorithm in Graph Theory! Kruskal's Algorithm is a fundamental method used to find the minimum spanning tree (MST) of a connected, undirected graph. Let's explore this important algorithm together! Contents [ hide ] Understanding the Problem Statement Before delving into Kruskal's Algorithm, let's understand the problem it addresses. In graph theory, a spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together without creating cycles. The minimum spanning tree (MST) of a graph is the spanning tree with the smallest possible sum of edge weights. The goal of Kruskal's Algorithm is to find this minimum spanning tree efficiently. What is Kruskal's Algorithm? Kruskal's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an empty graph and adds the edges with the smallest we...

Welcome to our beginner's guide to Dijkstra's Algorithm in Graph Theory! Dijkstra's Algorithm is a fundamental method used to find the shortest path between nodes in a graph, particularly in graphs with non-negative edge weights. Let's explore this powerful algorithm together! Contents [ hide ] Understanding the Problem Statement Before diving into Dijkstra's Algorithm, let's understand the problem it addresses. In graph theory, finding the shortest path between two vertices is a common task. This problem is particularly important in various applications such as network routing, transportation systems, and GPS navigation. The shortest path between two vertices in a graph is defined as the path with the minimum total edge weight. Dijkstra's Algorithm efficiently finds the shortest path from a source vertex to all other vertices in the graph. What is Dijkstra's Algorithm? Dijkstra's Algorithm is a greedy algorithm used to find the sh...

Welcome to our beginner's guide to Prim's Algorithm in Graph Theory! Prim's Algorithm is a fundamental method used to find the minimum spanning tree (MST) of a connected, undirected graph. Let's explore this important algorithm together! Contents [ hide ] Understanding the Problem Statement Before delving into Prim's Algorithm, let's understand the problem it addresses. In graph theory, a spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together without creating cycles. The minimum spanning tree (MST) of a graph is the spanning tree with the smallest possible sum of edge weights. The goal of Prim's Algorithm is to find this minimum spanning tree efficiently. What is Prim's Algorithm? Prim's Algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an arbitrary vertex and grows the spanning tree by adding the shortest e...

Welcome to our beginner's guide to Topological Sort in Graph Theory! Topological Sort is an essential algorithm used to order the vertices of a directed graph such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Let's explore this important concept together! Contents [ hide ] Understanding the Problem Statement Before delving into Topological Sort, let's understand the problem it addresses. Consider a scenario where tasks depend on one another; for example, in a project where certain tasks must be completed before others can begin. Such dependencies can be modeled using directed graphs, where nodes represent tasks and directed edges represent dependencies between tasks. The goal of Topological Sort is to find a linear ordering of the vertices of the graph such that for every directed edge uv, the vertex u comes before the vertex v in the ordering. This ordering provides a sequence in which the tasks can be perf...