Longest Consecutive Sequence in an Unsorted Array

Question

You are given an Array of numbers and they are unsorted/random order. You are supposed to find the longest sequence of consecutive numbers in the array. Note the sequence need not be in sorted order within the array. Here is an example :

Input :

A[] = {10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101}

Output is :

{16,17,18,19,20,21,22}

The solution needs to be of O(n) complexity.

I am told that the solution involves using a hash table and I did come across few implementations that used 2 hash tables. One cannot sort and solve this because sorting would take O(nlgn) which is not what is desired.

"longest consecutive sequence of numbers" - that would be the whole list. — Thorbjørn Ravn Andersen, Sep 17 '11 at 07:35
@Thorbj0m - How is that possible ? The whole iist isn't entirely made up on consecutive numbers placed in an unsorted/random manner right ? — Anoop Menon, Sep 17 '11 at 07:38
Seeing as they are integers, you *can* sort in O(n) time, and from there it's kind of trivial. — harold, Sep 17 '11 at 09:09
@harold - Order (n) sorting ? - please explain your sorting algorithm — Anoop Menon, Sep 17 '11 at 10:12
radix sort, counting sort, bucket sort, take your pick. Pure comparison sorts aren't going to get better than O(n log n) of course but there's a lot more that you can do with integers than just compare them. — harold, Sep 17 '11 at 10:19
These are sorting algorithms which require one to know the start and end range of elements present in an array which is a big constraint. If I was not clear in my question, the set of elements would not give the programmer any prior information of the start/end range of elements present — Anoop Menon, Sep 17 '11 at 10:25
Radix sort only needs the elements to be of constant size to get O(n), and they are. — harold, Sep 17 '11 at 10:33
As @Dietrich Epp metioned that, if it's a homework mark it as home work, we can do this but it's better do it yourself before closing, also show us what you tryed with using hash or any other idea. — Saeed Amiri, Sep 17 '11 at 11:05
@Saeed Amiri - Thanks. I'll take care of that in the future :) — Anoop Menon, Sep 17 '11 at 11:06
Simply Aj - Harold is right that radix sort only needs the elements to be of constant size, but even if you needed to know the max/min values in order to sort (e.g., bucket sort), determining max and min are O(n) processes, so that doesn't slow anything down. — Ted Hopp, Sep 18 '11 at 02:00

Jon Skeet · Answer 1 · 2011-09-17T09:12:07.050

14

You could have two tables:

Start table: (start-point, length)
End table: (ending-point, length)

When adding a new item, you would check:

Does value + 1 exist in start table? If so, delete it and create a new entry of (value, length + 1) where length is the "current" length. You'd also update the end table with the same end point but greater length.
Does value - 1 exist in the end table? If so, delete it and create a new entry of (value, length + 1), and this time update the start table (the starting position will be the same, but the length will be increased)

If both conditions hold, then you're effectively stitching two existing sequences together - replace the four existing entries with two new entries, representing the single longer sequence.

If neither condition holds, you just create a new entry of length 1 in both tables.

After all the values have been added, you can just iterate over the start table to find the key with the largest value.

I think this would work, and would be O(n) if we assume O(1) hash lookup/add/delete.

EDIT: C# implementation. It took a little while to get right, but I think it works :)

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        Dictionary<int, int> starts = new Dictionary<int, int>();
        Dictionary<int, int> ends = new Dictionary<int, int>();

        foreach (var value in input)
        {
            int startLength;
            int endLength;
            bool extendsStart = starts.TryGetValue(value + 1,
                                                   out startLength);
            bool extendsEnd = ends.TryGetValue(value - 1,
                                               out endLength);

            // Stitch together two sequences
            if (extendsStart && extendsEnd)
            {
                ends.Remove(value + 1);
                starts.Remove(value - 1);
                int start = value - endLength;
                int newLength = startLength + endLength + 1;
                starts[start] = newLength;
                ends[start + newLength - 1] = newLength;
            }
            // Value just comes before an existing sequence
            else if (extendsStart)
            {
                int newLength = startLength + 1;
                starts[value] = newLength;
                ends[value + newLength - 1] = newLength;
                starts.Remove(value + 1);
            }
            else if (extendsEnd)
            {
                int newLength = endLength + 1;
                starts[value - newLength + 1] = newLength;
                ends[value] = newLength;
                ends.Remove(value - 1);
            }
            else
            {
                starts[value] = 1;
                ends[value] = 1;
            }
        }

        // Just for diagnostics - could actually pick the longest
        // in O(n)
        foreach (var sequence in starts)
        {
            Console.WriteLine("Start: {0}; Length: {1}",
                              sequence.Key, sequence.Value);
        }
    }
}

EDIT: Here's the single-hashset answer implemented in C# too - I agree, it's simpler than the above, but I'm leaving my original answer for posterity:

using System;
using System.Collections.Generic;
using System.Linq;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        HashSet<int> values = new HashSet<int>(input);

        int bestLength = 0;
        int bestStart = 0;
        // Can't use foreach as we're modifying it in-place
        while (values.Count > 0)
        {
            int value = values.First();
            values.Remove(value);
            int start = value;
            while (values.Remove(start - 1))
            {
                start--;
            }
            int end = value;
            while (values.Remove(end + 1))
            {
                end++;
            }

            int length = end - start + 1;
            if (length > bestLength)
            {
                bestLength = length;
                bestStart = start;
            }
        }
        Console.WriteLine("Best sequence starts at {0}; length {1}",
                          bestStart, bestLength);
    }
}

edited Sep 17 '11 at 09:12

answered Sep 17 '11 at 07:41

Jon Skeet

1,421,763
867
9,128
9,194

Thanks @Jon ! However I have a doubt that if we desire O(1) complexity for our hash lookups wouldn't that mean that our hash buckets will consume memory ? Let's say we have a million numbers in the array and we need to perform this algorithm over it. – Anoop Menon Sep 17 '11 at 07:50
@Anoop: It would probably still be amortized O(1), but it would indeed take quite a lot of memory. I confess the details of hash table implementations are somewhat beyond me, but so long as there aren't hash *collisions* I believe it should be okay. I could be mistaken, of course. I doubt that you'll find any solutions based on hash tables which *don't* rely on O(1) hash operations. – Jon Skeet Sep 17 '11 at 07:55
Wouldn't this algorithm output {start 16, length 3} for the array given in the question? ...which is how I actually understood the question, too. But it seems there are elements allowed within the consecutive list that are not part of the consecutive list. – DaveFar Sep 17 '11 at 08:00
@DaveBall: Why would it not spot that 20 is present in the longest sequence? Before reaching 20 it would have { start=16, length=4 } and { end = 19, length = 4 }, as well as { start = 21, length = 2 } and { end = 22, length = 2 }. It would then notice that 20 stitched together those sequences. – Jon Skeet Sep 17 '11 at 08:06
Oh, you are right. I'm taking it back and claiming the opposite ;) – DaveFar Sep 17 '11 at 08:14
@Jon - Now the stich operation you mention where you remove 4 entries and replace it with 2. Say in your example to DaveBall once you are done with start and end tables for 20, it would mean { end = 19, length = 5 } and { start = 20, length = 3 }. Now what is the cost for the stich operation ? This could be O(n+k) where k is proportional to the number of consecutive elements present in the original array right ? – Anoop Menon Sep 17 '11 at 08:24
@Simply Aj: No, the stitch operation is still cheap - it's updating two entries and removing two. There's only one entry per sequence, not per value in the sequence. I've updated my answer with some C# code, and it seems to work for the example input data. (Btw, changing your name makes it harder to get comment notification to work...) – Jon Skeet Sep 17 '11 at 08:32
I think it's simpler to accumulate all the data into a single hash set before doing any 'analysis', and then check and eliminate the runs in a single pass. You don't need to worry about keeping track or merging intervals this way because you've waited until they've naturally joined at the end, and you only need one hash set. – Rob Neuhaus Sep 17 '11 at 08:34
@rrenaud: I don't see how that works, given that a hash set is unordered. I'll be happy to be proved wrong though - I'll look forward to your answer :) – Jon Skeet Sep 17 '11 at 08:35
@Jon - Sorry about the name change - wasn't aware of it's implications. Will take care of it from now on. I'll go through the code and get back if I haven't understood it, else thanks a lot :) – Anoop Menon Sep 17 '11 at 08:40
@rrenaud: Actually, I think I might see what you mean after all - will do it when I get home. – Jon Skeet Sep 17 '11 at 08:43
1

I posted my solution with working code in an answer. – Rob Neuhaus Sep 17 '11 at 08:51
@rrenaud: Cool - I've added a C# version to my answer, too. – Jon Skeet Sep 17 '11 at 09:02
@Jon - The second solution rocks ! :) The first solution too I got it except I am a bit confused if startLength (2), endLength (4) prior to getting called would be 3 and 5 respectively while you enter the 'if (extendsStart && extendsEnd)' section. But to the stich to work as per your code it would be 2 and 4 respectively :) – Anoop Menon Sep 17 '11 at 10:05
@Simply Aj: When stitching, `endLength` is the length of the sequence which *ends* just before `value`, and `startLength` is the length of the sequence which *starts* just after `value`. I'm not sure exactly what your example is meant to be about, but it really does work :) As for the second solution - well, it's just my implementation of someone else's idea... – Jon Skeet Sep 17 '11 at 10:15
@Jon - I was not contesting if your solution works; merely was clearing my doubt. Actually I should have observed that you are doing 'TryGetValue' which would not have changed the value of endLength and startLength across function calls - my folly :) Yes I observed rrenaud's insistence that one hash is enough – Anoop Menon Sep 17 '11 at 10:22
@Simply Aj: TryGetValue *does* always set endLength and startLength, as I'm using them as out parameters - but I only ever go into *one* of the four blocks on each iteration, only ever using values which have been correctly set. – Jon Skeet Sep 17 '11 at 10:23
@Jon - Okay :) I am completely illiterate with the intricacies of C#. I only happen to know C :) – Anoop Menon Sep 17 '11 at 10:26
@Jon - I can think one more improvisation over this. Instead of tracking +1 and -1 one, we can do in one direction and as and when we encounter a consecutive number we could delete it and increment the count in array[val]. But before deleting array[val+x] where x >= 1, we will store in array[va] the max(array[val], array[val+x]) where x >=1 . – Anoop Menon Sep 19 '11 at 03:40
@Simply Aj: sorry, I didn't really follow that... but if it works for you, great :) – Jon Skeet Sep 19 '11 at 05:27

Henry Z · Answer 2 · 2011-09-17T08:11:23.437

7

Dump everything to a hash set.

Now go through the hashset. For each element, look up the set for all values neighboring the current value. Keep track of the largest sequence you can find, while removing the elements found from the set. Save the count for comparison.

Repeat this until the hashset is empty.

Assuming lookup, insertion and deletion are O(1) time, this algorithm would be O(N) time.

Pseudo code:

 int start, end, max
 int temp_start, temp_end, count

 hashset numbers

 for element in array:
     numbers.add(element)

 while !numbers.empty():
     number = numbers[0]
     count = 1
     temp_start, temp_end = number 

     while numbers.contains(number - 1):
         temp_start = number - 1; count++
         numbers.remove(number - 1)

     while numbers.contains(number + 1):
         temp_end = number + 1; count++
         numbers.remove(number + 1)

     if max < count:
         max = count
         start = temp_start; end = temp_end

 max_range = range(start, end)

The nested whiles don't look pretty, but each number should be used only once so should be O(N).

edited Sep 17 '11 at 08:11

answered Sep 17 '11 at 07:44

Henry Z

163
8

Pretty neat except for one part which I am missing out. How will I find the starting of the sequence if I keep deleting the 'n-1' element in the sequence because I found 'n' in the hash already ? – Anoop Menon Sep 17 '11 at 07:57
@Anoop I added pseudo code, hopefully it's more clear now – Henry Z Sep 17 '11 at 08:05
The first addition to the hash is O(n). Now for each number in the hash you are iterating 'x' times in the decremental direction and 'y' times to the incremental direction. The while within a while is almost unavoidable in your solution making it > O(n) right ? albeit by a constant k where k is proportional to the number of consecutive elements present in the original set. However Jon's solution 'k' seems to be throttled by the fact that both 'start' and 'end' table operations evaluate to true. – Anoop Menon Sep 17 '11 at 08:25
1

You need to update number inside the erase loops. – Rob Neuhaus Sep 17 '11 at 08:32
@renaud - count++ is done inside the loops if that is what you are referring to – Anoop Menon Sep 17 '11 at 10:08
@Simply the solution should still be O(n) since it goes through each number once. The loops are deceiving because they also remove numbers. – NullUserException Sep 17 '11 at 14:36
rrenaud is right -- currently both those inner `while` loops are stuck looking for the same `number - 1` on each iteration! Otherwise a nice solution – j_random_hacker Sep 17 '11 at 14:55

score 5 · Accepted Answer · answered Sep 17 '11 at 08:50

Here is a solution in Python that uses just a single hash set and doesn't do any fancy interval merging.

def destruct_directed_run(num_set, start, direction):
  while start in num_set:
    num_set.remove(start)
    start += direction
  return start

def destruct_single_run(num_set):
  arbitrary_member = iter(num_set).next()
  bottom = destruct_directed_run(num_set, arbitrary_member, -1) 
  top = destruct_directed_run(num_set, arbitrary_member + 1, 1)
  return range(bottom + 1, top)

def max_run(data_set):
  nums = set(data_set)
  best_run = []
  while nums:
    cur_run = destruct_single_run(nums)
    if len(cur_run) > len(best_run):
      best_run = cur_run
  return best_run

def test_max_run(data_set, expected):
  actual = max_run(data_set)
  print data_set, actual, expected, 'Pass' if expected == actual else 'Fail'

print test_max_run([10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101], range(16, 23))
print test_max_run([1,2,3], range(1, 4))
print max_run([1,3,5]), 'any singleton output fine'

I am having a little trouble understanding the python code and the range() argument you opted to pass. — Anoop Menon, Sep 17 '11 at 10:19
@AnoopMenon test_max_run is a unit-test and the range is the expected range that max_run should return for the data_set. — hgf, Aug 11 '13 at 01:03

score 2 · Answer 4 · answered Apr 05 '12 at 11:43

Another solution is with hash search which runs in O(n)

int maxCount = 0;
for (i = 0; i<N; i++) 
{ 
    // Search whether a[i] - 1 is present in the list.If it is present, 
    // you don't need to initiate count since it  will be counted when 
    // (a[i] - 1) is traversed.
    if (hash_search(a[i]-1))
        continue;

    // Now keep checking if a[i]++ is present in the list, increment the count
    num = a[i]; 
    while (hash_search(++num)) 
        count++;

    // Now check if this count is greater than the max_count got previously 
    // and update if it is
    if (count > maxCount)
    {
        maxIndex = i;
        count = maxCount;
    }
}

score 1 · Answer 5 · edited Feb 26 '13 at 16:23

class Solution {
public:
    struct Node{
        int lower;
        int higher;
        Node(int l, int h):lower(l),higher(h){

    }
};
int longestConsecutive(vector<int> &num) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    map<int,Node> interval_map;
    map<int,Node>::iterator curr_iter,inc_iter,des_iter;

    //first collect
    int curr = 0;
    int max = -1;
    for(size_t i = 0; i < num.size(); i++){
        curr = num[i];
        curr_iter = interval_map.find(curr);
        if (curr_iter == interval_map.end()){
            interval_map.insert(make_pair(curr,Node(curr,curr)));
        }
    } 
    //the next collect    
    for(curr_iter = interval_map.begin(); curr_iter != interval_map.end(); curr_iter++)
    {
        int lower = curr_iter->second.lower;
        int higher = curr_iter->second.higher;
        int newlower = lower, newhigher = higher;

        des_iter = interval_map.find(lower - 1);
        if (des_iter != interval_map.end())
        {
            curr_iter->second.lower = des_iter->second.lower;
            newlower = des_iter->second.lower;
        }

        inc_iter = interval_map.find(higher + 1);
        if (inc_iter != interval_map.end()){
            curr_iter->second.higher = inc_iter->second.higher;
            newhigher = inc_iter->second.higher;
        }

        if (des_iter != interval_map.end()){
            des_iter->second.higher = newhigher;
        }
        if (inc_iter != interval_map.end()){
            inc_iter->second.lower = newlower;
        }
        if (curr_iter->second.higher - curr_iter->second.lower + 1> max){
             max = curr_iter->second.higher - curr_iter->second.lower + 1;
         }
    }   
    return max;
}
};

Thanks for posting an answer! While a code snippet could answer the question it's still great to add some addition information around, like explain, etc .. — j0k, Feb 26 '13 at 16:19

score 1 · Answer 6 · answered Sep 17 '11 at 08:17

Here is the implementation:

static int[] F(int[] A)
{
    Dictionary<int, int> low = new Dictionary<int, int>();
    Dictionary<int, int> high = new Dictionary<int, int>();

    foreach (int a in A)
    {
        int lowLength, highLength;

        bool lowIn = low.TryGetValue(a + 1, out lowLength);
        bool highIn = high.TryGetValue(a - 1, out highLength);

        if (lowIn)
        {
            if (highIn)
            {
                low.Remove(a + 1);
                high.Remove(a - 1);
                low[a - highLength] = high[a + lowLength] = lowLength + highLength + 1;
            }
            else
            {
                low.Remove(a + 1);
                low[a] = high[a + lowLength] = lowLength + 1;
            }
        }
        else
        {
            if (highIn)
            {
                high.Remove(a - 1);
                high[a] = low[a - highLength] = highLength + 1;
            }
            else
            {
                high[a] = low[a] = 1;
            }
        }
    }

    int maxLow = 0, maxLength = 0;
    foreach (var pair in low)
    {
        if (pair.Value > maxLength)
        {
            maxLength = pair.Value;
            maxLow = pair.Key;
        }
    }

    int[] ret = new int[maxLength];
    for (int i = 0; i < maxLength; i++)
    {
        ret[i] = maxLow + i;
    }

    return ret;
}

Thanks ! Good one, but the solution with a single hash bucket is relatively better :) Check out Jon's and rrenaud's solutions. Thanks once again Peter — Anoop Menon, Sep 17 '11 at 10:07

score 0 · Answer 7 · answered Jul 11 '13 at 20:26

This is the solution of Grigor Gevorgyan from a duplicate of this question, but I think simplified:

data = [1,3,5,7,4,6,10,3]

# other_sides[x] == other end of interval starting at x
# unknown values for any point not the end of an interval
other_sides = {}
# set eliminates duplicates, and is assumed to be an O(n) operation
for element in set(data):
    # my intervals left hand side will be the left hand side
    # of an interval ending just before this element
    try:
        left = other_sides[element - 1]
    except KeyError:
        left = element

    # my intervals right hand side will be the right hand side
    # of the interval starting just after me
    try:
        right = other_sides[element + 1]
    except KeyError:
        right = element

    # satisfy the invariants
    other_sides[left] = right
    other_sides[right] = left

# convert the dictionary to start, stop segments
# each segment is recorded twice, so only keep half of them
segments = [(start, stop) for start, stop in other_sides.items() if start <= stop]
# find the longest one
print max(segments, key = lambda segment: segment[1] - segment[0])

score 0 · Answer 8 · edited May 23 '17 at 12:23

Here's python code based by answer by Grigor Gevorgyan for similar question, I think it's very elegant solution of that problem

l = [10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101]
d = {x:None for x in l}
print d
for (k, v) in d.iteritems():
    if v is not None: continue
    a, b = d.get(k - 1), d.get(k + 1)
    if a is not None and b is not None: d[k], d[a], d[b] = k, b, a
    elif a is not None: d[a], d[k] = k, a
    elif b is not None: d[b], d[k] = k, b
    else: d[k] = k
    print d

m = max(d, key=lambda x: d[x] - x)
print m, d[m]

output:

{2: 2, 67: None, 100: None, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: None, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 100, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 10, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 11, 11: 10, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 12, 11: 10, 12: 10, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 12, 11: 10, 12: 10, 45: 45, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 16, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 17, 17: 16, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 18, 17: 16, 18: 16, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 19, 17: 16, 18: 16, 19: 16, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 20, 17: 16, 18: 16, 19: 16, 20: 16, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 21, 17: 16, 18: 16, 19: 16, 20: 16, 21: 16, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 22, 17: 16, 18: 16, 19: 16, 20: 16, 21: 16, 22: 16}
16 22

Longest Consecutive Sequence in an Unsorted Array

8 Answers8

Linked

Related