July 2024 – My Programming Notes

Monthly Archives: July 2024

C# || How To Restore Array From Adjacent Pairs Using C#

July 28, 2024 admin No comments

The following is a module with functions which demonstrates how to restore the array from adjacent pairs using C#.

1. Restore Array – Problem Statement

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n – 1 where each adjacentPairs[i] = [u_i, v_i] indicates that the elements u_i and v_i are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]] Output: [1,2,3,4] Explanation: This array has all its adjacent pairs in adjacentPairs. Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]] Output: [-2,4,1,-3] Explanation: There can be negative numbers. Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]] Output: [100000,-100000]

2. Restore Array – Solution

The following is a solution which demonstrates how to restore the array from adjacent pairs.





		
		
			2. Restore Array - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to restore the array from adjacent pairs
// ============================================================================
public class Solution {
    public int[] RestoreArray(int[][] adjacentPairs) {
        var graph = new Dictionary<int, List<int>>();

        foreach (int[] edge in adjacentPairs) {
            int x = edge[0];
            int y = edge[1];

            if (!graph.ContainsKey(x)) {
                graph[x] = new List<int>();
            }

            if (!graph.ContainsKey(y)) {
                graph[y] = new List<int>();
            }

            graph[x].Add(y);
            graph[y].Add(x);
        }

        int root = 0;
        foreach (int num in graph.Keys) {
            if (graph[num].Count == 1) {
                root = num;
                break;
            }
        }

        int curr = root;
        int[] ans = new int[graph.Count];
        ans[0] = root;
        int i = 1;
        int prev = int.MaxValue;

        while (i < graph.Count) {
            foreach (int neighbor in graph[curr]) {
                if (neighbor != prev) {
                    ans[i] = neighbor;
                    i++;
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }

        return ans;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jul 28, 2024
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to restore the array from adjacent pairs
// ============================================================================
public class Solution {
    public int[] RestoreArray(int[][] adjacentPairs) {
        var graph = new Dictionary<int, List<int>>();
 
        foreach (int[] edge in adjacentPairs) {
            int x = edge[0];
            int y = edge[1];
 
            if (!graph.ContainsKey(x)) {
                graph[x] = new List<int>();
            }
 
            if (!graph.ContainsKey(y)) {
                graph[y] = new List<int>();
            }
 
            graph[x].Add(y);
            graph[y].Add(x);
        }
 
        int root = 0;
        foreach (int num in graph.Keys) {
            if (graph[num].Count == 1) {
                root = num;
                break;
            }
        }
 
        int curr = root;
        int[] ans = new int[graph.Count];
        ans[0] = root;
        int i = 1;
        int prev = int.MaxValue;
 
        while (i < graph.Count) {
            foreach (int neighbor in graph[curr]) {
                if (neighbor != prev) {
                    ans[i] = neighbor;
                    i++;
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }
 
        return ans;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,2,3,4] [-2,4,1,-3] [100000,-100000]

Monthly Archives: July 2024

C# || How To Restore Array From Adjacent Pairs Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories