Solving Three Medium-Level Coding

In this article, we will explore three medium-level coding problems and provide solutions for each of them. The problems we will discuss are:

1. Minimum Number of Vertices to Reach All Nodes
2. Maximum Twin Sum of a Linked List
3. Swap Nodes in Pairs

While these problems may appear unrelated at first, they share common characteristics and can enhance our understanding of various programming concepts. Furthermore, by exploring their solutions, we can gain insights into graph theory, linked list manipulation, and algorithmic problem-solving techniques. Therefore, this article aims to provide readers with a comprehensive overview of these problems and their solutions.

Problem 1: Minimum Number of Vertices to Reach All Nodes Description

The problem involves a directed acyclic graph (DAG) represented by an array of edges. The task is to find the smallest set of vertices from which all nodes in the graph are reachable. It is guaranteed that a unique solution exists.

Solution

To solve this problem, we can utilize the concept of in-degree and out-degree vertices in a DAG. We iterate through all the edges and identify the vertices with zero in-degree. These vertices will form the minimum set of vertices needed to reach all other nodes in the graph.

fun findSmallestSetOfVertices(n: Int, edges: List<List<Int>>): List<Int> {

    val inDegree = IntArray(n)

    for (edge in edges) {

        val to = edge[1]

        inDegree[to]++

    }

    

    val result = mutableListOf<Int>()

    for (i in 0 until n) {

        if (inDegree[i] == 0) {

            result.add(i)

        }

    }

    

    return result

}

Similarities With Other Problems

The Minimum Number of Vertices problem shares similarities with graph traversal and topological sorting algorithms. Therefore, by understanding its solution, we can gain insights into concepts like in-degree, out-degree, and graph connectivity.

Problem 2: Maximum Twin Sum of a Linked List Description

In this problem, we are given a linked list of even length, where each node has a twin. The twin of the ith node is the (n-1-i)th node, where n is the total number of nodes in the list. The twin sum is defined as the sum of a node and its twin.

Solution

To find the maximum twin sum of the linked list, we iterate through half of the linked list and calculate the sum of each node and its twin. By keeping track of the maximum sum encountered, we can find the desired result.

class ListNode(var `val`: Int) {

    var next: ListNode? = null

}



fun maxTwinSum(head: ListNode?): Int {

    var current = head

    var maxSum = 0



    while (current != null && current.next != null) {

        maxSum = maxOf(maxSum, current.`val` + current.next!!.`val`)

        current = current.next!!.next

    }



    return maxSum

}

Similarities With Other Problems

The Maximum Twin Sum problem involves linked list manipulation and understanding node relationships. By solving this problem, we enhance our understanding of linked list traversal and arithmetic operations on linked list nodes.

Problem 3: Swap Nodes in Pairs Description

Given a linked list, the task is to swap every two adjacent nodes and return the head of the modified list. Only the nodes themselves can be changed, and the values within the nodes must remain unaltered.

Solution

To solve this problem, we employ a recursive approach. We swap the first two adjacent nodes and recursively call the function on the remaining linked list. By appropriately adjusting the pointers, we can swap the nodes in pairs throughout the list.

class ListNode(var `val`: Int) {

    var next: ListNode? = null

}



fun swapPairs(head: ListNode?): ListNode? {

    if (head?.next == null) {

        return head

    }



    val newHead = head.next

    head.next = swapPairs(newHead?.next)

    newHead?.next = head



    return newHead

}

Similarities With Other Problems

The Swap Nodes in Pairs problem involves linked list manipulation and recursive algorithms. By solving this problem, we develop a deeper understanding of linked list traversal, pointer manipulation, and recursive problem-solving techniques.

Conclusion 

In this article, we explored three medium-level coding problems: Minimum Number of Vertices to Reach All Nodes, Maximum Twin Sum of a Linked List, and Swap Nodes in Pairs. Despite their apparent differences, these problems share common characteristics and help us strengthen our understanding of graph theory, linked list manipulation, and algorithmic problem-solving techniques. Furthermore, by examining their solutions, we acquire valuable insights into various programming concepts. Whether you are interested in graph algorithms, linked list manipulation, or recursive approaches, this article provides a useful resource for enhancing your problem-solving skills.