LeetCode 30 day Challenge #7 - Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them seperately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

C++ Solution:

class Solution {
public:
    int countElements(vector<int>& arr) {
        unordered_map<int, int> _map;
        
        for(int a : arr){
            if(_map.find(a) != _map.end())
                _map[a]++;
            else
                _map[a] = 1;
        }
        
        int result = 0;
        for(auto n : _map){
            if(_map.find(n.first + 1) != _map.end())
                result += n.second;
        }
        
        return result;
    }
};

Detailed Explanation on Youtube:

LeedCcode 30 day Challenge #2 - Happy Numbers

LeetCode 202 - Happy Numbers

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Detailed Explanation with 2 different methods in following video:

LeetCode 30 day Challenge #1 : Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

---

C++

1

class Solution {

2

public:

3

    int singleNumber(vector<int>& nums) {

4

        int result = 0;

5

        for(int n : nums)

6

            result ^= n;

7

8

        return result;

9

    }

10

};

LeetCode 286: Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

 3  -1   0   1
 2   2   1  -1
 1  -1   2  -1
 0  -1   3   4

Solution C++

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define INF 100


void push_to_queue(vector<vector<int>>& rooms, queue<pair<int, int>>& q, int x, int y, int d){
    if(x >= 0 && x < rooms.size() && y >= 0 && y < rooms[0].size() && rooms[x][y] > d){
       q.push({x, y});
       rooms[x][y] = d;
    }
}

void bfs(vector<vector<int>>& rooms, int i, int j, int dist){
    queue<pair<int, int>> gates;
    gates.push({i, j});
    while(!gates.empty()){
       int count = gates.size();
       for(int _x = 0; _x < count; ++_x){
           pair<int, int> pos = gates.front();
           gates.pop();
           int x = pos.first;
           int y = pos.second;
           push_to_queue(rooms, gates, x, y+1, dist+1);
           push_to_queue(rooms, gates, x, y-1, dist+1);
           push_to_queue(rooms, gates, x+1, y, dist+1);
           push_to_queue(rooms, gates, x-1, y, dist+1);
       }
       dist++;
    }
}

void wallsAndGates(vector<vector<int>>& rooms) {
    for(int i = 0; i < rooms.size(); ++i){
       for(int j = 0; j < rooms[0].size(); ++j){
          if(!rooms[i][j])
             bfs(rooms, i, j, 0);
       }
    }
}

void print_rooms(vector<vector<int>> rooms){
    for(int i = 0; i < rooms.size(); ++i){
       for(int j = 0; j < rooms[0].size(); ++j){
           cout << rooms[i][j] << "\t";
       }
       cout << "\n";
    }
    cout << "-------------------\n";
}

int main() {
    vector<vector<int>> rooms = {
           {INF, -1, 0, INF},
           {INF, INF, INF, -1},
           {INF, -1, INF, -1},
           {0, -1, INF, INF}
    };
    print_rooms(rooms);
    wallsAndGates(rooms);
    print_rooms(rooms);
 
    return 0;
}