Leetcode Study Day 22

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
 

Constraints:

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

My solution

My solution is using a map to store the value in the array as the key and the index as the value. If the map already contains the key, we check if the difference between the current index and the index stored in the map is less than or equal to k. If it is, then we return true. If not, we update the value of the key in the map to the current index. If the map does not contain the key, we add the key and value to the map. If we finish the loop, we return false.

Code

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map <int, vector<int>> numberMap;
        for (int i = 0; i < nums.size(); i++){
            if (numberMap[nums[i]].size()>0){
                if(i- numberMap[nums[i]][0] <= k)
                    return true;
                else
                    numberMap[nums[i]].pop_back();
            }
            numberMap[nums[i]].push_back(i);
        }
        return false;
    }
};

Difference between map and unordered_map

I also see some solutions with unordered_map. So I did some research on the difference between map and unordered_map.
Both std::map and std::unordered_map are associative containers in C++ that store elements in key-value pairs, but they have some fundamental differences in terms of their internal workings, performance characteristics, and functionalities:

1. Underlying Data Structure:

   • std::map: Implemented using a balanced tree (usually a red-black tree). This guarantees that the elements are always ordered by their keys.
   • std::unordered_map: Implemented using a hash table. The elements are not ordered.

2. Order of Elements:

   • std::map: The elements are always ordered according to the keys (based on the comparison function, which is operator< by default).
   • std::unordered_map: There is no order guarantee for the keys or the values.

3. Performance:

   • std::map:
     • Insertion, deletion, and search have a logarithmic complexity: (O(\log n)).
   • std::unordered_map:
     • In average cases, the insertion, deletion, and search have constant time complexity: (O(1)).
     • In the worst case (when there are hash collisions), these operations can degrade to (O(n)).

4. Hash Function:

   • std::map: Does not use hashing, so there’s no need for a hash function.
   • std::unordered_map: Uses a hash function to map keys to buckets. You can provide a custom hash function, but there’s a default one provided for most standard types.

5. Memory Overhead:

   • std::map: Typically has a lesser memory overhead compared to std::unordered_map because it doesn’t need to manage the hash table.
   • std::unordered_map: Might have more memory overhead due to managing the hash table, especially when the load factor increases.

6. Iterators:

   • std::map: Iterators are ordered and remain valid as long as the corresponding element exists in the map. Inserting or deleting elements does not invalidate iterators to other elements.
   • std::unordered_map: Iterators are not ordered. Inserting an element might invalidate iterators if rehashing occurs, but erasing an element only invalidates the iterator to that element.

7. Usage Scenarios:

   • std::map: Useful when you need to maintain an order (like when you need the smallest or largest key frequently) or when you need to work with operations that rely on order (e.g., finding elements in a range).
   • std::unordered_map: Useful when you need faster average-case insertion, deletion, and search times, and you don’t need the keys to be ordered.

In summary, the choice between std::map and std::unordered_map depends on the specific requirements of your application. If ordering is essential, go with std::map. If you need faster average-time operations and don’t care about order, std::unordered_map might be the better choice.

I’d like to share my third year project experience with you. It is to use Mitsuba, which is a physical based renderer to simulate the chenrenkov particles in the Europe Large Hadron Collider, which is in CERN. The reason that I did this is because for now, the experiences in CERN are simulated by Geant4, which is a Monte Carlo simulation toolkit. However, Geant4 is very slow and cost huge memory usage. In the end, with collaborating with students in the department of physics, our application reduce over 99% time and only cost less than 1mb memory usage with the same accuracy.

The challanges I faced out is that I knew nothing about the particle physics since my major is computer science. So in the beginning of the project, it’s tough for me to understand what the result should be look like and how to achieve it. In the team, everyone has their own role. Mine is to implement the Mitsuba renderer and the interface between Mitsuba and Geant4, wheareas my colleagues’ are study the physical theory of Cherenkov radiation. The method that I overcame the challange is to communicate with my colleagues frequently and ask them questions. We held weekly meetings and in the meeting, we shared our new progress and discussed the problems we met. If they have any questions about the Mitsuba, they will ask me. If I have any questions about the physical theory, I will ask them.

This project is meaningful for me because it is not a toy tool. It is a real application that can be used in the future. We also attend the sharing meeting in CERN and got a lot of positive feedbacks.

At the beginning of choosing my third year project, I noticed that there are large amount of resources consumed and cost has always been a problem with simulation experiments based on the report of usage of computing resources by CERN. Therefore, I got the idea to reduce simulation time by using other tools.

My step to develop this idea is firstly, shared this idea with my supervisor. She is very supportive and told me that the department of physics is also interested in this topic. Then I contacted the department of physics and we decided to collaborate together. After that, I started to learn Mitsuba and implemented the Mitsuba renderer and the interface between Mitsuba and Geant4. My colleagues studied the physical theory of Cherenkov radiation. In the end, we combined our work together and got the final result.

It was important to be innovative in this instance because it is the first time that Mitsuba is used to simulate the Cherenkov radiation. Before that, Geant4 is the only tool that can be used to simulate the Cherenkov radiation. Also, the tool we developed can be used in real life, it is different from the tools that I developed before, which are just for fun or course projects. I’m motivated to do this project because I want to do something meaningful and useful. I want to use my knowledge to help others.