Coding Challenge #6: First Duplicate

Resources Community Tutorials
#1

Coding Challenge #6

Welcome back, to another coding challenge! I’ve been getting some feedbacks telling me that the challenges are becoming somewhat very easy, for an experienced individual to say the least. Which is not necessarily bad, in fact it’s good because more people can contribute that way, but I’ll try to vary the difficulty in future challenges!

As usual, same requirements:

  • Has to be written in Lua 5.1 (the version roblox uses)
  • The program has to be compatible with Roblox Studio, meaning you can’t use features vanilla Lua has but rbxlua disabled
  • You can’t use httpservice to cheat the challenge

Given an array of positive integers, write a function firstDuplicate to find the first integer that is repeated at least once. If no duplicate is found return -1. Examples:

{1,2,3,1} --1
{2,1,4,2,4} --2
{12,4,5,9,15,12,2} --12
{1,2,3,4,5} -- -1

Here is a function to generate random number for you

local function random()
  local n = math.random(1, 20)
  local t = table.create(n)
  for i = 1, n do
    t[i] = math.random(1, n)
  end
  return t
end

Note that, you can see that the integers inside of the table are between 1 and the size of the table, meaning we don’t have an integer that’s greater than the table’s size. See if you can use that for your advantage!

Goodluck! You can find a list of all the challenges here or a github version here.
98e6477fa0a6a4ff482b43177d1c8e2abbc4d9df

Answer!

I simply make a table toLookFor to keep track of the integers that we’ve seen, and we loop through the table and each time make an arbitrary value (true for example) inside of toLookFor at the index corresponding with the current integer, and as well each time we loop we check if a true exists in toLookFor[current integer] which means that we have already seen this integer.

local function firstDuplicate(t)
  local toLookFor = {}
  for i, v in pairs(t) do
    if toLookFor[v] then
      return v
    end
    toLookFor[v] = true
  end
  return -1
end

Another way to do it is using table.find(), and see if after the current index there is a similar integer.

local function firstDuplicate(t)
  local toLookFor = {}
  for i, v in pairs(t) do
     if table.find(t, v, i+1) then
       return v
     end
  return -1
end

A golf code driven answer using the table.find method

function f(t)for i=1,#t do if table.find(t,t[i],i+1)then return t[i]end end return-1 end

Now for the creative answer. Remember when I told you?

Note that, you can see that the integers inside of the table are between 1 and the size of the table, meaning we don’t have an integer that’s greater than the table’s size. See if you can use that for your advantage!

What you can do is using this fact for your advantage: since there is no way an integer inside of the table can be greater then the table’s size, technically any integer can describe an index inside of that table. Each time we visit an integer, we go to the index that it’s supposed to represent in that table, and we negate the value at that index, as a way of saying “we have seen an integer that leads back to this index”. Like that, each time we visit an integer, we check if the index that it leads to is already negative, if it is already negative that means a previous integer led to the same index thus they’re equal, and return that. Brilliant!

local function firstDuplicate(t)
     for i, v in pairs(t) do
          t[math.abs(v)] = -t[math.abs(v)] --negate it, t[v] is the index v leads to, we do math.abs because there is a chance that the value we visited has already been tagged which means it's negative, and we can't index with negative integers.
          if t[v] < 0 then --we check if the value of the index that it leads to is positive, because technically if we negated it/flipped its sign and got a positive number as a result, that means it was previously negative, which means it was tagged and return the current integer
              return v
          end
     end
     return -1
end
12 Likes
#2

This is pretty simple compared to the other ones:

local tab = {"shake", "it", "off", "...ready", "for", "it", "?"}

local function findDup(tb)
	
	local tabl = {}
	
	for i, v in ipairs(tb) do
		
		if not table.find(tabl, v) then
			
			table.insert(tabl, v)
			
		else
			
			return v
			
		end
		
	end
	
	return nil
	
end

print(findDup(tab)) --it

Y’all Swifties know what I’m talkin’ about, right?

2 Likes
#3

Well it was supposed to work with integers, but goodjob! I do recommend checking out the answers I gave, especially the third one, because it’s really interesting and will surely give you inspiration.

3 Likes
#4

Without looking at the answer, here’s what I did:

local function FindFirstDupe(tab)
	local newTable = {}
	for i = 1, #tab do
		if table.find(newTable, tab[i]) then
			return tab[i]
		else
			table.insert(newTable, i)
		end
	end
	return -1
end

print(FindFirstDupe({1, 2, 4, 2, 3, 5, 4})) --prints 2 yay
print(FindFirstDupe({1, 2, 3, 4, 5, 6, 9})) --prints -1 yay

This is pretty much the same as @TheCarbyneUniverse’s answer, actually.

1 Like
#5

Here was my approach:

local function findDup(ignoredindex, Table)
	local val = Table[ignoredindex]

	for i = ignoredindex+1, #Table do
		if Table[i] == val then
			return true
		end
	end

	return nil
end


local function firstDupp(Table)
	for i, element in ipairs(Table) do
		if findDup(i, Table) then
			return element
		end
	end
	return -1
end

print(firstDupp({1, 2, 3, 1}))
print(firstDupp({2, 1, 4, 2, 4}))

I did not know that table.find() had a third parameter that I could use, hence why I made the findDup() function. This is certainly not the faster/most efficient technique, but it works nevertheless.

1 Like
#6

This probably isn’t the best approach, but it should work fine:

code 
local function firstDuplicate(array)
	local found = {}

	for _, value in ipairs(array) do
		if table.find(found, value) then
			return value
		else
			found[#found + 1] = value
		end
	end

	return -1
end

Since this was another relatively easy challenge, I decided to also do a version that allows you to specify where to start searching. It turned out to not really be much harder, but oh well.

code 
local inext = ipairs{}

local function firstDuplicate(array, start)
	local found = {}
	start = start - 1
	
	for _, value in inext, array, start do
		if table.find(found, value) then
			return value
		else
			found[#found + 1] = value
		end
	end

	return -1
end
4 Likes
#7

Here is my apporach (I know, this is very long):

function getDuplicateIntegers(IntegersTable)
	local duplicate
	for i, v in pairs(IntegersTable) do
	    local number = IntegersTable[i]

		for k, v in pairs (IntegersTable) do
	        if v == number and k ~= i then
		        duplicate = v
		    return duplicate end
	    end
	end
	if duplicate ~= nil then
		return duplicate
	else
		return -1
	end
end

EDIT: I noticed it works with any kind of value lol

1 Like
#8
code 

 function getFirstDuliplicate(array)
	local cache = {}
	for _, v in ipairs(array) do
	 if cache[v] then
	  return v
	 end
	 cache[v] = true
	end
end

—

function getFirstDuliplicate(array)
	table.sort(array)
	for i, v in ipairs(array) do
		if table.find(array, v, i + 1) then
			return v
		end
	end
end

sorry for bad indent

This challenge reminded me of this:

:joy:

5 Likes
#9

Very interesting! Everything he mentions is actually related, how he uses hashmaps, since lua table’s are a hybrid of hashtables and arrays, that allows to have efficient O(1) lookups, using the cache auxilary table you have. Also the time and space complexities! The challenge he’s doing requires O(n^2) time complexity, which is basically a for loop inside of a for loop which us what he’s doing, and O(1) space complexity because he’s not using a table to store info or anything. In all of our code samples we have O(n) for both time and space complexity!

2 Likes
#10

Here’s my attempt at it:

local function firstDuplicate(array)
	local found = {}
	
	for i, v in ipairs(array) do
		if found[v] then
			return "Duplicate: "..v
		end

		found[v] = true
	end
	return -1 -- return -1 since we know that there were no duplicates because if they were, this statement would be unreachable
end

print(firstDuplicate({1, 2, 3, 0})) --> -1
print(firstDuplicate({1, 2, 3, 1})) --> Duplicate: 1
1 Like
#12

There’s probably a better way, here is my version:

local function firstDuplicate(t1)
	for _,v in ipairs(t1) do
		local first = false

		for _, v2 in ipairs(t1) do
			if v2 == v then
				if not first then
					first = true
				else
					return v
				end
			end
		end
	end
	
	return -1
end
1 Like
#13 
local function firstDuplicate(list)
	local store = {}
	for _,element in pairs(list) do
		if store[element] then
			return element
		else
			store[element] = "Stored"
		end
	end
	return -1
end

local lists = {
	{1,2,3,1}, --1
	{2,1,4,2,4}, --2
	{12,4,5,9,15,12,2}, --12
	{1,2,3,4,5}, -- -1
}

for _,list in pairs(lists) do
	print(firstDuplicate(list))
end