LeetCode 01. Two Sum

🧩 PROBLEM - LeetCode 01. Two Sum

LINK: https://leetcode.com/problems/two-sum/description/

Given an array of integers, return indices of the two numbers such that they add up to target. There would have exactly one solution, and you may not use the same element twice.

Example.

Input: nums = [5,7,1,7], target = 14

Output: [1,3]

Explanation: Because nums[1] + nums[3] == 14, we return [1,3]

Constraints:

2 <= nums.length <= $10^4$

-$10^9$ <= nums[i] <= $10^9$

-$10^9$ <= target <= $10^9$

---

Problem anaylsis

1. DataType = “int” -> valid
2. nums.length -> time complex should be O($n^2$) ~ O(n)
3. nums.length -> space complex should be O(n)

• Brute force: Check all combination
• At least checking O(n)
• some elements of array don’t need it because the number is larger than target
  • But if we have negative value, it does not work
• if using sort, the time complexity is O(n $\log{n}$) but it is breaking all of index.
• making pair of number and index, time and space complexity are O(n).

Miss Check list

• There are positive and negatvie, so if we sort, should consider the negative features.
• Sometimes sorting cost is more bigger than all of the ideal process.
• The relationship of just two can solve another way
• I didn’t understand enough about hash algorithm “unordered_map”

# NOT WORKING -> just positive value array.
# pair -> sort -> decide the highest limit index
    std::vector<int> nums;
    int target;

    std::vector<std::pair<int, int>> vctMappingInput;
    {
        int i32Size = (int)nums.size();
        int* pI32Num = nums.data();

        for (int i = 0; i < i32Size; ++i)
        {
            vctMappingInput.emplace_back(*pI32Num, i);
            ++pI32Num;
        }
    }

    std::sort(vctMappingInput.begin(), vctMappingInput.end(), [](std::pair<int, int>& a, std::pair<int, int>& b)
        {
            return a.first < b.first;
        });

    int i32MaxIndex = (int)vctMappingInput.size() - 1;
    {
        for (int i = 0; i <= i32MaxIndex; ++i)
        {
            if (vctMappingInput[i].first > target)
            {
                i32MaxIndex = i;
                break;
            }
        }
    }

    std::vector<int> vctResult;
    bool bOK = false;

    for (int i = 0; i <= i32MaxIndex; ++i)
    {
        for (int j = i + 1; j <= i32MaxIndex; ++j)
        {
            if (vctMappingInput[i].first + vctMappingInput[j].first == target)
            {
                vctResult.push_back(vctMappingInput[i].second);
                vctResult.push_back(vctMappingInput[j].second);
                bOK = true;
                break;
            }
        }

        if (bOK)
            break;
    }

# WORKING -> both positive and negative value array.
# pair -> sort -> low/high cursor with minimizing searching
# processing time = 6ms -> not enough

    std::vector<std::pair<int, int>> vctMappingInput;
    {
        int i32Size = (int)nums.size();
        int* pI32Num = nums.data();

        for (int i = 0; i < i32Size; ++i)
        {
            vctMappingInput.emplace_back(*pI32Num, i);
            ++pI32Num;
        }
    }

    std::sort(vctMappingInput.begin(), vctMappingInput.end(), [](std::pair<int, int>& a, std::pair<int, int>& b)
        {
            return a.first < b.first;
        });

    std::vector<int> vctResult;
    int i32ResultLowIdx = -1;
    int i32ResultHighIdx = -1;

    int i32LowIdx = 0;
    int i32HighIdx = (int)vctMappingInput.size() - 1;
    bool bOK = false;

    while (1)
    {
        i32HighIdx = (int)vctMappingInput.size() - 1;

        if (i32LowIdx == i32HighIdx)
            break;

        int i32LowValue = vctMappingInput[i32LowIdx].first;
        int i32HighValue = vctMappingInput[i32HighIdx].first;
        bool bConvert = false;

        if (i32LowValue + i32HighValue == target)
        {
            i32ResultLowIdx = i32LowIdx;
            i32ResultHighIdx = i32HighIdx;
            bOK = true;
        }

        if (i32LowValue + i32HighValue > target)
        {
            for (int i = i32HighIdx - 1; i > i32LowIdx; --i)
            {
                i32HighValue = vctMappingInput[i].first;

                if (i32LowValue + i32HighValue == target)
                {
                    i32ResultLowIdx = i32LowIdx;
                    i32ResultHighIdx = i;
                    bOK = true;
                    break;
                }
                else if (i32LowValue + i32HighValue < target)
                    break;
            }

        }

        if (bOK)
            break;
        
        i32LowIdx++;
    }

    vctResult.push_back(vctMappingInput[i32ResultLowIdx].second);
    vctResult.push_back(vctMappingInput[i32ResultHighIdx].second);

USE Hash Table

#include <iostream>
#include <vector>

class HashTable
{
public:
	HashTable();

public:
	bool Insert(int i32Key, int i32Value);
	bool Erase(int i32Key);
	bool Find(int i32Key, int& i32Value);
	bool IsFind(int i32Key);

private:
	int MakeHash(int i32Key);

public:
	std::vector<std::vector<std::pair<int, int>>> vctTable;
};

HashTable::HashTable()
{
	vctTable.resize(16);
}

bool HashTable::Insert(int i32Key, int i32Value)
{
	int i32Idx = MakeHash(i32Key);

	vctTable[i32Idx].emplace_back(i32Key, i32Value);

	return true;
}

bool HashTable::Erase(int i32Key)
{
	int i32Idx = MakeHash(i32Key);
	std::vector < std::pair<int, int>>& vctData = vctTable[i32Idx];

	for (int i = 0; i < (int)vctData.size(); ++i)
	{
		if (vctData[i].first == i32Key)
		{
			vctData[i] = vctData.back();
			vctData.pop_back();
			break;
		}
	}

	return true;
}

bool HashTable::Find(int i32Key, int& i32Value)
{
	bool bReturn = false;

	do
	{
		int i32Idx = MakeHash(i32Key);
		
		std::vector < std::pair<int, int>>& vctData = vctTable[i32Idx];

		for (int i = 0; i < (int)vctData.size(); ++i)
		{
			if (vctData[i].first == i32Key)
			{
				i32Value = vctData[i].second;
				bReturn = true;
				break;
			}
		}


	} 
	while (false);

	return bReturn;
}

bool HashTable::IsFind(int i32Key)
{
	int i32Dummy;

	return Find(i32Key, i32Dummy);
}

int HashTable::MakeHash(int i32Key)
{
	int i32Size = (int)vctTable.size();

	return (i32Key % i32Size + i32Size) % i32Size;
}

int main()
{
	std::vector<int> nums;
	int target;
	HashTable mapList;

	std::vector<int> vctResult;

	for (int i = 0; i < (int)nums.size(); ++i)
	{
		int i32Key = target - nums[i];
		int i32Value;

		if (mapList.Find(i32Key, i32Value))
		{
			vctResult.push_back(i32Value);
			vctResult.push_back(i);
			break;
		}

		mapList.Insert(nums[i], i);
	}

	return 0;
}

For simple implementation, i use fixed hash table size and simple hash i make. So i can see the hash table’s performance is important.

---

---

Anaylsis

• CHECK SCOPE -> INPUT SIZE
  • Under Hundred: O($2^n$)
  • Under thousand : O($n^2$)
  • Under 10K: O(N $\log{N}$)
  • Under 1M ~ over: O( $\log{n}$)
• COMPLEXITY
  • Time complexity
  • Space complexity
• Check Valid DataType
  • Overflow
• SIMULATION
  • Check test case by myself
• Compare with other people solutions

---

---