O(n)

Method 3 - Using LinkedHashSet for order preservation

We can use LinkedHashSet instead.

Use a LinkedHashSet to store all distinct elements (elements that have not been seen before).
Use a HashSet to keep track of elements that have already been seen more than once.
Iterate through the array and perform the checks and insertions accordingly.
Finally, retrieve the k-th distinct element from the LinkedHashSet.

Code

[{"language":"Java","code":"class Solution {\n\n\tpublic String kthDistinct(String[] arr, int k) {\n\t\tLinkedHashSet<String> distincts = new LinkedHashSet<>();\n\t\tHashSet<String> duplicates = new HashSet<>();\n\n\t\tfor (String str: arr) {\n\t\t\tif (!duplicates.contains(str)) {\n\t\t\t\tif (!distincts.contains(str)) {\n\t\t\t\t\tdistincts.add(str);\n\t\t\t\t} else {\n\t\t\t\t\tdistincts.remove(str);\n\t\t\t\t\tduplicates.add(str);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\tif (distincts.size()<k) {\n\t\t\treturn \"\";\n\t\t}\n\n\t\tIterator<String> iterator = distincts.iterator();\n\n\t\tint count = 0;\n\n\t\twhile (iterator.hasNext()) {\n\t\t\tcount++;\n\t\t\tString element = iterator.next();\n\n\t\t\tif (count == k) {\n\t\t\t\treturn element;\n\t\t\t}\n\t\t}\n\n\t\treturn \"\";\n\t}\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tpublic</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> String </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">kthDistinct</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">String</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">arr</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">\t\tLinkedHashSet&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">String</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> distincts </span><span style=\"color:#D73A49;--shiki-dark:#F97583

Related Tags