<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
    public:
class aset {
private:
   struct Node {
      int data;
      Node* left;
      Node* right;
      int height;
      Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
   };
   int32_t S = 0;
    Node* R_Rot(Node* y) {  if (!y || !y->left) return y; Node* x = y->left;
        Node* T2 = x->right; x->right = y; y->left = T2;
        if (y)  y->height = 1 + max(y->left ? y->left->height : 0, y->right ? y->right->height : 0);
        if (x) x->height = 1 + max(x->left ? x->left->height : 0, x->right ? x->right->height : 0);
        return x;
    } Node* L_Rot(Node* x) { if (!x || !x->right) return x; Node* y = x->right;
        Node* T2 = y->left; y->left = x; x->right = T2;
        if (x) x->height = 1 + max(x->left ? x->left->height : 0, x->right ? x->right->height : 0);
        if (y)  y->height = 1 + max(y->left ? y->left->height : 0, y->right ? y->right->height : 0);
        return y;
    }

Node* insertNode(Node* node, int key) {
       if (node == nullptr) {
           S++; 
           return new Node(key);
       }

       if (key < node->data)
           node->left = insertNode(node->left, key);
       else if (key > node->data)
           node->right = insertNode(node->right, key);
       else
           return node;

       node->height = 1 + max(node->left ? node->left->height : 0, node->right ? node->right->height : 0);
        int32_t balance = node ? (node->left ? node->left->height : 0) - (node->right ? node->right->height : 0) : 0;

       // Balancing the node
       if (balance > 1 && key < node->left->data)
           return R_Rot(node);

       if (balance < -1 && key > node->right->data)
           return L_Rot(node);

       if (balance > 1 && key > node->left->data) {
           node->left = L_Rot(node->left);
           return R_Rot(node);
       }

       if (balance < -1 && key < node->right->data) {
           node->right = R_Rot(node->right);
           return L_Rot(node);
       }

       return node;
   }


public:
    Node* root;
    aset() : root(nullptr) {}
    void insert(int key) {
        root = insertNode(root, key);
    }
    int32_t size() const {
      return S;
    }
};
    bool containsDuplicate(vector<int>& ar) {
        aset m;
        for(auto i : ar) m.insert(i);
        if(ar.size() != m.size()) 
        return true;
        return false;
    }
};
68365