SDE - Intern

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices without any cycles and with the minimum possible total edge weight.

A spanning tree’s weight is the sum of the weights of each edge in the spanning tree.

You have been given a connected undirected weighted graph having 'n' vertices, from 1 to 'n', and 'm' edges.

You are given an array 'edges' of size 'm', containing the details of the edges of the graph.

Each element of 'edges' contains three integers, the two vertices that are being connected and the weight of the edge.

Find the weight of the minimum spanning tree of the given graph.

Example :

Input: 'n' = 5, 'm' = 6
'edges' = [[1, 2, 6], [2, 3, 5], [3, 4, 4], [1, 4, 1], [1, 3, 2], [3, 5, 3]]

Output: 11

Explanation: The given graph is:

The minimum spanning tree of the graph is:

And its weight is 1 + 2 + 5 + 3 = 11.

Ninja has found his new passion for photography. He has clicked some really good photos but in one of his images, he doesn’t like the color of a particular region. So, he decides to change the color of that region. Can you help him with this task?

The image is represented in the form of a 2D array of size M * N. Each pixel in the image is a positive integer. Ninja has given you the coordinates (row and column) of a certain pixel and the new color value. You need to replace the color of the given pixel and all adjacent same-colored pixels with the new color.

Note:

Two pixels are adjacent if they are connected to each other in any of the four directions: up, down, left, or right.

Diagonal pixels are not considered adjacent.

Example:

Consider the image of size 4*4, shown below (left). Let the coordinates of the starting pixel are (1, 2) and the new color is 8. The starting pixel, highlighted with red color, has a pixel value of 3. 

On replacing the given pixel and all adjacent same-colored pixels with the new color we get the new image, shown below (right). The modified pixels are highlighted with green color.