LeetCode Solution: Number of Good Paths

 Question: There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.

You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

A good path is a simple path that satisfies the following conditions:

The starting node and the ending node have the same value.

All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node's value should be the maximum value along the path).

Return the number of distinct good paths.

Note that a path and its reverse are counted as the same path. For example, 0 -> 1 is considered to be the same as 1 -> 0. A single node is also considered as a valid path.

Constraints:

• n == vals.length
• 1 <= n <= 3 * 104
• 0 <= vals[i] <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges represents a valid tree.

 

Solution: To solve this problem, you can use a depth-first search (DFS) algorithm to traverse the tree, starting from each node. For each node, you can check whether the path from that node to any of its descendant nodes satisfies the conditions for a good path. If it does, you can increment a counter variable.

This algorithm first convert the input edge list to adjacency list to traverse the tree easily. Then it iterates over all the nodes and for each node it calls a dfs function to traverse the tree and check the conditions for good path. If the path is good it increments the counter variable. Finally, it returns the count of good paths.

class Solution { int[] parents; private int find(int x){ if(x != parents[x]) parents[x] = find(parents[x]); return parents[x]; } public int numberOfGoodPaths(int[] vals, int[][] edges) { int n = vals.length; if(n == 1) return 1; // 1. init union find and ids arrayList parents = new int[n]; List<Integer> ids = new ArrayList<>(); for(int i = 0; i < n; i++){ parents[i] = i; ids.add(i); } // build Graph Map<Integer, Set<Integer>> graph = new HashMap<>(); for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; graph.putIfAbsent(u, new HashSet<>()); graph.putIfAbsent(v, new HashSet<>()); graph.get(u).add(v); graph.get(v).add(u); } // 2. sort the ids by vals Collections.sort(ids, (a, b) -> (vals[a] - vals[b])); // 3. iterate from smallest to biggest int ret = 0; for (int i = 0; i < n; i++) { // get all same vals of node ids[i, j) int j = i + 1; while(j < n && vals[ids.get(j)] == vals[ids.get(i)]) j++; // enum each same val for (int k = i; k < j; k++) { int x = ids.get(k); // traverse neighbor, if small than current node for(int neighbor : graph.get(x)){ if (vals[x] >= vals[neighbor]) { // union node x and its smaller neighbor parents[find(x)] = find(neighbor); } } } // checkout for current values, the # of val in each component Map<Integer, Integer> temp = new HashMap<>(); for(int k = i; k < j; k++){ int root = find(ids.get(k)); temp.put(root, temp.getOrDefault(root, 0) + 1); // # of current val in the {root} group } // standalone nodes for (int v : temp.values()){ ret += v * (v + 1) / 2; } i = j - 1; } return ret; } }

class Solution { int[] parents; private int find(int x){ if(x != parents[x]) parents[x] = find(parents[x]); return parents[x]; } public int numberOfGoodPaths(int[] vals, int[][] edges) { int n = vals.length; if(n == 1) return 1; // 1. init union find and ids arrayList parents = new int[n]; List<Integer> ids = new ArrayList<>(); for(int i = 0; i < n; i++){ parents[i] = i; ids.add(i); } // build Graph Map<Integer, Set<Integer>> graph = new HashMap<>(); for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; graph.putIfAbsent(u, new HashSet<>()); graph.putIfAbsent(v, new HashSet<>()); graph.get(u).add(v); graph.get(v).add(u); } // 2. sort the ids by vals Collections.sort(ids, (a, b) -> (vals[a] - vals[b])); // 3. iterate from smallest to biggest int ret = 0; for (int i = 0; i < n; i++) { // get all same vals of node ids[i, j) int j = i + 1; while(j < n && vals[ids.get(j)] == vals[ids.get(i)]) j++; // enum each same val for (int k = i; k < j; k++) { int x = ids.get(k); // traverse neighbor, if small than current node for(int neighbor : graph.get(x)){ if (vals[x] >= vals[neighbor]) { // union node x and its smaller neighbor parents[find(x)] = find(neighbor); } } } // checkout for current values, the # of val in each component Map<Integer, Integer> temp = new HashMap<>(); for(int k = i; k < j; k++){ int root = find(ids.get(k)); temp.put(root, temp.getOrDefault(root, 0) + 1); // # of current val in the {root} group } // standalone nodes for (int v : temp.values()){ ret += v * (v + 1) / 2; } i = j - 1; } return ret; } }

class Solution {

    int[] parents;

    private int find(int x){

        if(x != parents[x]) 

            parents[x] = find(parents[x]);

        return parents[x];

    }

    public int numberOfGoodPaths(int[] vals, int[][] edges) {

        int n = vals.length;

        if(n == 1) return 1;

        parents = new int[n];

        List<Integer> ids = new ArrayList<>();

        for(int i = 0; i < n; i++){

            parents[i] = i;

            ids.add(i);

        }

        Map<Integer, Set<Integer>> graph = new HashMap<>();

        

        for (int[] edge : edges) {

            int u = edge[0];

            int v = edge[1];

            

            graph.putIfAbsent(u, new HashSet<>());

            graph.putIfAbsent(v, new HashSet<>());

            

            graph.get(u).add(v);

            graph.get(v).add(u);

        }

        Collections.sort(ids, (a, b) -> (vals[a] - vals[b]));

        int ret = 0;

        for (int i = 0; i < n; i++) {

            int j = i + 1;

            while(j < n && vals[ids.get(j)] == vals[ids.get(i)]) j++;

            for (int k = i; k < j; k++) {

                int x = ids.get(k);

                for(int neighbor : graph.get(x)){

                    if (vals[x] >= vals[neighbor]) {

                        parents[find(x)] = find(neighbor);

                    }

                }

            }

            Map<Integer, Integer> temp = new HashMap<>();

            for(int k = i; k < j; k++){

                int root = find(ids.get(k));

                temp.put(root, temp.getOrDefault(root, 0) + 1);  // # of current val in the {root} group

            }

            for (int v : temp.values()){

                ret += v * (v + 1) / 2;

            }

            

            i = j - 1;

        }

        

        return ret;

    }

}

LeetCode Solution: Longest Path With Different Adjacent Characters

 Question: You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Constraints:

• n == parent.length == s.length
• 1 <= n <= 10^5
• 0 <= parent[i] <= n - 1 for all i >= 1
• parent[0] == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.

Solution: You can solve this problem using dynamic programming.

• Create an array dp of size n, where dp[i] represents the longest path ending at node i that satisfies the given condition.
• Initialize dp[i] as 1 for all i, since every node itself is a valid path of length 1.
• Iterate through the nodes in the tree in a bottom-up fashion, starting from the leaf nodes and working towards the root. For each node i, iterate through its children j and update dp[i] as follows:

                If s[i] is different from s[j], dp[i] = max(dp[i], dp[j] + 1)

• Return the maximum value in the dp array.

Note that, in this solution, the time complexity is O(n) and the space complexity is O(n) as well.

class Solution {

    public int longestPath(int[] parent, String s) {

        int n = parent.length;

        int[] dp = new int[n];

        Arrays.fill(dp, 1);

        

        for (int i = n - 1; i >= 0; i--) {

            for (int j = 0; j < n; j++) {

                if (parent[j] == i && s.charAt(i) != s.charAt(j)) {

                    dp[i] = Math.max(dp[i], dp[j] + 1);

                }

            }

        }

        int max = 0;

        for (int i = 0; i < n; i++) {

            max = Math.max(max, dp[i]);

        }

        return max;

    }

}

LeetCode Solution: Same Tree

 Question: Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

Solution: This solution first checks if both trees are empty, in which case they are the same. If only one of the trees is empty, they are not the same. If the values of the nodes are different, the trees are not the same. Otherwise, the function recursively checks the left and right subtrees.

class Solution {

    public boolean isSameTree(TreeNode p, TreeNode q) {

        // If both trees are empty, they are the same

        if (p == null && q == null) {

            return true;

        }

        // If only one tree is empty, they are not the same

        if (p == null || q == null) {

            return false;

        }

        // If the values of the nodes are different, the trees are not the same

        if (p.val != q.val) {

            return false;

        }

        // Check the left and right subtrees recursively

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }

}

LeetCode Solution: Max Points on a Line

 Question: Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solution: 

To solve this problem, you can iterate through each point in the array and check how many other points lie on the same straight line with it. You can do this by calculating the slope between the two points and checking if the slope is the same for all other points.

import java.util.HashMap;

import java.util.Map;

class Solution {

    public int maxPoints(int[][] points) {

        int maxPoints = 0;

        for (int i = 0; i < points.length; i++) {

            int samePoints = 1;

            Map<String, Integer> slopeCount = new HashMap<>();

            for (int j = 0; j < points.length; j++) {

                if (i == j) {

                    continue;

                }

                int dx = points[i][0] - points[j][0];

                int dy = points[i][1] - points[j][1];

                if (dx == 0 && dy == 0) {

                    samePoints++;

                    continue;

                }

                int gcd = gcd(dx, dy);

                String slope = (dy / gcd) + "/" + (dx / gcd);

                slopeCount.put(slope, slopeCount.getOrDefault(slope, 1) + 1);

            }

            int sameSlopePoints = samePoints;

            for (int count : slopeCount.values()) {

                sameSlopePoints = Math.max(sameSlopePoints, count);

            }

            maxPoints = Math.max(maxPoints, sameSlopePoints);

        }

        return maxPoints;

    }

    private static int gcd(int a, int b) {

        if (b == 0) {

            return a;

        }

        return gcd(b, a % b);

    }

}

LeetCode Solution: Maximum Ice Cream Bars question

Question: It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the ith ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible. 

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Solution: This solution first sorts the costs array in ascending order, and then iterates through the costs array. For each cost, it checks if the cost is less than or equal to the available coins. If it is, it adds one to the maximum number of ice cream bars and subtracts the cost from the available coins. If the cost is greater than the available coins, the loop is broken and the maximum number of ice cream bars is returned.

public class IceCreamBars {

    public int maximumIceCreamBars(int[] costs, int coins) {

        // Sort the costs array in ascending order

        Arrays.sort(costs);

        

        // Initialize the maximum number of ice cream bars to 0

        int maxIceCreamBars = 0;

        

        // Iterate through the costs array

        for (int cost : costs) {

            // If the current cost is greater than the available coins, break the loop

            if (cost > coins) {

                break;

            }

            // Otherwise, add one to the maximum number of ice cream bars and subtract the cost from the available coins

            maxIceCreamBars++;

            coins -= cost;

        }

        

        return maxIceCreamBars;

    }

}

GitHub and Bitbucket: An Overview of Two Popular Version Control Systems and Their Commands

    GitHub and Bitbucket are two popular version control systems that are widely used by developers to manage and collaborate on their code. Both systems are based on Git, which is a distributed version control system that makes it possible for programmers to keep track of and manage changes to their codebase. In this article, we will take a look at what GitHub and Bitbucket are, and we will explore the various commands that you can use with these systems to manage your code.

GitHub is a web-based version control system that is owned by Microsoft. It is widely used by developers to host and manage their code repositories, and it offers a range of features that make it easy to collaborate on projects. GitHub allows developers to create public and private repositories, and it offers a number of tools for managing and reviewing code, such as pull requests and code reviews.

Bitbucket is another web-based version control system that is owned by Atlassian. Like GitHub, it is used by developers to host and manage their code repositories, and it offers a range of features for collaboration and code management. Bitbucket differs from GitHub in that it offers both cloud-based and self-hosted options, which allows developers to choose the option that best fits their needs.

Both GitHub and Bitbucket are based on Git, and they support many of the same commands. Some of the basic commands that you can use with these systems include:

• "git init": This command is used to initialize a new Git repository. It creates a new .git directory in your project folder, which is used to store all of the information about your repository.

• "git clone": This command is used to create a local copy of a remote repository. This is useful if you want to work on a project that is hosted on a remote server, such as GitHub or Bitbucket. To clone a repository, you simply need to specify the URL of the repository that you want to clone.

• "git add": This command is used to stage changes for commit. It adds the specified files to the staging area, which is a temporary holding area where changes are stored before they are committed to the repository. You can use the 'git add' command to stage individual files or entire directories.

• "git commit": This command is used to commit changes to the repository. It records your changes in the repository, along with a message that describes the changes. It is important to include a descriptive message with each commit, as it will help you and others to understand the changes that were made.

These are just a few of the basic commands that you can use with Git. There are many other commands that you can use to manage your code, such as "git diff," which shows the differences between two versions of your code, and "git merge," which allows you to combine the changes from multiple branches of your code.

In summary, GitHub and Bitbucket are popular version control systems that are based on Git and offer a range of features for managing and collaborating on code. Whether you are a beginner or an experienced developer, these systems offer a number of tools and commands that can help you to manage your code and collaborate with others on projects.

Exploring JavaScript's Amazing Features: A Versatile Programming Language for Web Applications

 JavaScript is a popular programming language which is widely used to build web-based applications and websites. It is known for its versatility and ability to run on a wide range of platforms, and it offers a number of cool features that make it a powerful tool for developers. In this article, we will take a look at some of the cool features of JavaScript and how it is used to build modern web applications.

One of the most impressive features of JavaScript is its ability to run on the client-side, which means that it can be executed directly in the user's web browser. This allows developers to build interactive and responsive applications that can run in the browser without the need for a server. JavaScript can be used to create a wide range of interactive elements, such as drop-down menus, image galleries, and form validation.

JavaScript is also an object-oriented language, which means that it allows developers to define and manipulate objects in their code. This can make it easier to structure and organize complex applications, and it allows developers to reuse code and build more efficient and scalable applications.

In addition to these features, JavaScript also offers a wide range of tools and libraries that can be used to extend its functionality. For example, you can use JavaScript frameworks such as React and Angular to build powerful and interactive web applications, and you can use libraries such as jQuery to simplify common tasks such as manipulating the DOM (Document Object Model) and making AJAX (Asynchronous JavaScript and XML) requests.

Finally, JavaScript is constantly evolving, and new versions of the language are regularly released to add new features and capabilities. The latest version of JavaScript, ECMAScript 2021, includes a number of new features that make it easier to build modern web applications, such as asynchronous iteration and the optional chaining operator.

In summary, JavaScript is a powerful and versatile programming language that is widely used to build modern web applications. Whether you are a beginner or an experienced developer, there is always something new to learn and discover with JavaScript, and it is an essential tool for anyone who is building web-based applications.

Exploring the Cool Features of HTML: The Standard Markup Language for Building Web Pages

HTML, or HyperText Markup Language, is the standard markup language for creating web pages and web applications. It is used to structure and format the content of a webpage, and it is an essential tool for anyone building websites or web-based applications. In this article, we will look at some of the cool features of HTML and how it is used to create modern web pages.

One of the most basic but powerful features of HTML is the ability to create and structure content using a wide range of elements. These elements can be used to create headings, paragraphs, lists, and many other types of content, and they can be styled using CSS to control their appearance. HTML also includes several special elements that can add multimedia content to a webpage, such as images, videos, and audio files.

Another cool feature of HTML is the ability to create links between web pages. With HTML, you can create links that allow users to navigate between different pages on your website or to other websites. You can also create anchors within a page that allow users to jump to specific sections of the page, which can be especially useful for longer pages.

HTML also includes several features that are designed to make it easier to build web-based applications. For example, you can use HTML forms to collect user input and send it to a server for processing. You can also use HTML to create interactive elements, such as buttons and drop-down menus, that allow users to interact with your application.

Finally, HTML constantly evolves, and new versions of the language are regularly released to add new features and capabilities. The latest version of HTML, HTML5, includes several new features that make it easier to build modern web applications, such as support for video and audio playback, improved support for mobile devices, and new elements for building interactive graphics.

In summary, HTML is a powerful and versatile tool for building modern web pages and web-based applications. Whether you are a beginner or an experienced developer, there is always something new to learn and discover with HTML. It is an essential tool for anyone building websites or web-based applications. 

Exploring the Cool Features of Springboot: A Java-Based Framework for Building Web Applications

 Springboot is a popular Java-based framework for building web applications. It is known for its simplicity & ease of use, and it offers a wide range of features that make it an efficient and valuable tool for developers. In this article, we will look at some of the cool features of Springboot that make it an attractive choice for building modern web applications.

One of the standout features of Springboot is its ability to get a new application up and running quickly. With just a few lines of code, you can create a new Springboot application ready to be deployed and used. This is possible thanks to Springboot's auto-configuration feature, which automatically configures your application based on the dependencies you have added. This means you can start a new project quickly without spending much time configuring your application.

Another cool feature of Springboot is its support for microservices. Microservices are a popular architecture pattern that involves building applications as a collection of small, independent services. With Springboot, creating and deploying microservices is easy, and you can use the framework to manage the communication between your microservices. This can make it easier to build and maintain large, complex applications comprising many different services.

Springboot also includes several features that make building and testing your applications more accessible. For example, the framework consists of built-in support for testing, including unit testing and integration testing. This can make it easier to ensure that your application is working as expected and catch any issues before deploying it.

In addition to these features, Springboot also offers a range of tools and plugins that can be used to extend its functionality. For example, you can use Springboot to build REST APIs, create web applications, and even build mobile applications using the Springboot mobile plugin.

Overall, Springboot is a powerful and feature-rich framework that offers many tools and features for building modern web applications. Whether you are a beginner or an experienced developer, there is a lot that you can do with Springboot. It is worth exploring if you are looking for a simple and easy-to-use framework for building web applications.

An Introduction to Git: Understanding the Version Control System and Its Commands

 Git is a version control system that is used by developers to track and manage changes to their code. It allows developers to collaborate on projects, revert back to previous versions of their code, and manage multiple versions of their codebase. In this article, we will take a look at what Git is and the various commands that you can use to manage your code.

Git is a distributed version control system, which means that it stores copies of your code on multiple computers rather than just a single central server. This allows developers to work on their code offline and makes it easier to collaborate on projects. Git stores the history of your code in a repository, which is a collection of files and directories that contains all of the information about your code.

There are a number of commands that you can use with Git to manage your code. Some of the most basic commands include:

• "git init": This command is used to initialize a new Git repository. It creates a new .git directory in your project folder, which is used to store all of the information about your repository.

• "git clone": This command is used to create a local copy of a remote repository. This is useful if you want to work on a project that is hosted on a remote server, such as GitHub. To clone a repository, you simply need to specify the URL of the repository that you want to clone.

• "git add": This command is used to stage changes for commit. It adds the specified files to the staging area, which is a temporary holding area where changes are stored before they are committed to the repository. You can use the "git add" command to stage individual files or entire directories.

• "git commit": This command is used to commit changes to the repository. It records your changes in the repository, along with a message that describes the changes. It is important to include a descriptive message with each commit, as it will help you and others to understand the changes that were made.

• "git push": Sends commits to a remote repository.

• "git pull": Updates the local repository with changes from a remote repository.

• "git branch": Manages branches in the local repository.

• "git stash": Temporarily saves changes that are not ready to be committed.

• "git log": Shows a history of commits in the current branch.

These are just a few of the basic commands that you can use with Git. There are many other commands that you can use to manage your code, such as "git diff," which shows the differences between two versions of your code, and "git merge," which allows you to combine the changes from multiple branches of your code.

In summary, Git is a powerful and widely-used version control system that allows developers to manage and collaborate on their code. Whether you are a beginner or an experienced developer, there is a lot that you can do with Git, and it is an essential tool for anyone who is working on code projects.

Comparing Angular and React: Understanding the Key Differences

Angular and React are two of the most popular JavaScript libraries for building web applications. Both libraries are widely used by developers and have a large and active community of users. However, there are some key major differences between the two libraries that you should be aware of if you are considering using one of them for your next project.

One of the main key differences between Angular and React is the way in which they are structured. Angular is a full-featured framework that provides a wide range of features and tools for building web applications. It includes a router, a template engine, a dependency injection system, and many other features that make it easy to build complex and scalable applications. React, on the other hand, is a smaller library that is focused solely on the view layer of an application. It provides a powerful set of tools for building reusable UI components, but it does not include many of the other features that are found in Angular.

Another key difference between Angular and React is the way in which they handle data binding. Angular uses two-way data binding, which means that changes made to the UI are automatically reflected in the underlying data model, and vice versa. React, on the other hand, uses a unidirectional data flow, which means that data flows in only one direction, from the parent component to the child component. This can make it easier to understand how data is flowing through an application and can help to prevent errors and bugs.

A third difference between Angular and React is the way in which they are used in the development process. Angular applications are typically built using a combination of HTML templates, JavaScript code, and CSS styles. React applications, on the other hand, are built using a syntax called JSX, which allows developers to write HTML-like code directly in their JavaScript code. This can make it easier for developers to build complex UI elements and can make it easier to understand the structure of an application.

In summary, Angular and React are both powerful tools for building web applications, but they have some key differences that you should be familiar with. Angular is a full-featured framework that is well-suited for building complex and scalable applications, while React is a smaller library that is focused solely on the view layer of an application. Both libraries have their own strengths and weaknesses, and the right choice for your project will depend on your specific needs and requirements.

Discover the Cool Things You Can Do with CSS

 CSS, or Cascading Style Sheets, is a stylesheet language that is used to represent the look & formatting of a document written in HTML. It allows developers to control the appearance of web pages by separating the content of a document from its presentation. CSS is a powerful tool that can be used to create a wide range of visual effects, and in this article, we will take a look at some of the cool things that you can do with CSS.

One of the most powerful features of CSS is its ability to control the layout of a webpage. With CSS, you can specify the position of elements on a page, control the size and dimensions of elements, and create complex grid-based layouts. This is particularly useful for creating responsive designs that look good on a wide range of devices.

CSS also offers a wide range of options for styling text. You can alternate the size, font, and color of text, add text shadows, and even animate text using CSS. This can be used to create visually appealing headlines and other text elements that draw the attention of your visitors.

In addition to styling text and layout, CSS also offers a range of options for styling images. You can use CSS to add borders, round the corners of images, and even apply filters to images. This can be used to create a wide range of visual effects and make your images stand out.

One of the coolest things that you can do with CSS is create animations. With CSS, you can animate elements on a webpage by changing their properties over time. This can be used to create a wide range of effects, such as fading elements in and out, moving elements around the page, and even creating complex interactive animations.

CSS is a powerful tool that allows developers to control the appearance of web pages in a variety of ways. Whether you are a beginner or an experienced developer, there is always something new to learn and discover with CSS. If you are interested in learning more about CSS and what it can do, there are a wide range of resources available online that can help you get started.