Pankaj Tanwar
Published on

Two Out of Three.

––– views

Welcome to yet-another 26th edition of my coding diary where I solve a coding challenge daily and share my thought process with some interesting ways to solve the problem.

Well, let's get started.

Problem of the day - Two Out of Three

Tag - Easy

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3] Output: [3,2]

The simplest explanation of the problem statement would be to find the numbers which are present in at least 2 arrays.

By looking at the problem, I could imagine of having three hashmaps to check, if a number is present in all three hashmaps or not. (I know, its the worst one! don't worry I will optimize it going forward)

Straight forward approach -

  • Maintain three hashmaps
  • Iterate over each array and set the values to their respective hashmap
  • Loop from 0 to 100 (max possible value as per the constraints) and find which element is present in at least 2 array

I am not going to write code for this approach. It's the simplest approach and the worst one.

In order to optimize it further, I re-read the problem statement and this time, constraints caught my attention. Max possible length and element of given arrays is 100.

Whenever, I get small constraints limit I think of using an array of fixed lengths instead of a heavy hashmap.

So, my new approach is to keep a 2D array of 3 rows and 100 columns. For each array, I will set the value in it's respective row.

Here is the code

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        int list[3][101] = {0};


        vector<int> res;
		// set value
        for(int num: nums1) list[0][num] = 1;
        for(int num: nums2) list[1][num] = 1;
        for(int num: nums3) list[2][num] = 1;


		// check if found in atleast 2
        for(int i=0;i<=100;i++) {
            if(list[0][i] + list[1][i] + list[2][i] >= 2) res.push_back(i);
        }
        return res;
    }
};

The code explains everything. (in case it's not, do reach out to me)

Umm, but I was not kind-of-satisfied with this approach. It's cool and working smoothly but let's find some other approach.

You guys are not gonna believe this but we can solve this with bit-masking too.

Idea behind the algorithm

  • Keep an array of fixed length
  • Forgiven first array, we XOR all elements with 1 (in binary 001), for the second array, XOR all elements with 2 (in binary 010), and for the third array, XOR all the elements with 4 (in binary 100).
  • If an element only appears once, possible values are 001, 010, 100. If the element appears twice possible values are 011, 101, 110 and if an element appears in all three arrays, possible values would be 111.
  • Here we can see if the final value for an element is 3,5,6,7 which means this element has appeared twice.

The code behind this interesting approach

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
	vector<int> res;
	int list[129] = {};
	for(int num: nums1) list[num] |= 1;
	for(int num: nums2) list[num] |= 2;
	for(int num: nums3) list[num] |= 4;


	for(int i=0;i<=100;i++) {
	    if(list[i] == 3 || list[i] >= 5) res.push_back(i);
	}


	return res;
    }
};

Another trick would be to directly check the number of set bits in the final value. If it's greater than equal to 2, we pick that answer.

It was a really-really nice problem to solve. I enjoyed the bit-masking approach. It motivates me to never settle for the brute-force approach. I would love to hear if you have any other approach to solve this.

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary

Tweet this article