<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* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        x->right = y;
        y->left = T2;
        y->height = max(height(y->left), height(y->right)) + 1;
        x->height = max(height(x->left), height(x->right)) + 1;
        return x;
    }
    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        y->left = x;
        x->right = T2;
        x->height = max(height(x->left), height(x->right)) + 1;
        y->height = max(height(y->left), height(y->right)) + 1;
        return y;
    }
    int height(Node* node) {
        return node ? node->height : 0;
    }
    int getBalance(Node* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }
Node* insertNode(Node* node, int key) {
       if (node == nullptr) {
           S++; // Increment size on successful insertion
           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; // Duplicate keys not allowed

       node->height = 1 + max(height(node->left), height(node->right));
       int balance = getBalance(node);

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

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

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

       if (balance < -1 && key < node->right->data) {
           node->right = rotateRight(node->right);
           return rotateLeft(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;
    }
};
68159