{"id":10119,"date":"2025-09-26T12:05:02","date_gmt":"2025-09-26T06:35:02","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10119"},"modified":"2025-09-26T14:54:27","modified_gmt":"2025-09-26T09:24:27","slug":"house-robber","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/house-robber\/","title":{"rendered":"House Robber"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\">\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n        You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and <strong>it will automatically contact the police if two adjacent houses were broken into on the same night<\/strong>.\n    <\/p>\n    \n    <p>\n        Given an integer array nums representing the amount of money of each house, return <i>the maximum amount of money you can rob tonight <strong>without alerting the police<\/strong><\/i>.\n    <\/p>\n\n\n    <h3>Example 1:<\/h2>\n    <p><strong>Input:<\/strong> nums = [1,2,3,1]<\/p>\n    <p><strong>Output:<\/strong> 4<\/p>\n    <p><strong>Explanation:<\/strong>  \n        Rob house 1 (money = 1) and then rob house 3 (money = 3).\nTotal amount you can rob = 1 + 3 = 4.\n    <\/p>\n\n    <h3>Example 2:<\/h2>\n    <p><strong>Input:<\/strong> nums = [2,7,9,3,1]<\/p>\n    <p><strong>Output:<\/strong> 12<\/p>\n    <p><strong>Explanation:<\/strong> Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.\n\n    <h3>Constraints<\/h3>\n    <ul>\n       <li><code>1 <= nums.length <= 100<\/code><\/li>\n       <li><code>0 <= nums[i] <= 400<\/code><\/li>\n    <\/ul>\n    \n<h2>Approach:<\/h2>\n<ul>\n    <li><strong>Choice at each house (i):<\/strong>\n    <ul>\n        <li>Either rob house i \u2192 then you must skip house i-1, so profit = val[i] + dp[i-2].<\/li>\n        <li>Or <strong><\/strong> i \u2192 then profit = dp[i-1]<\/li>\n        <li>Take maximum of the two. <code>dp[i]=max(val[i]+dp[i\u22122],dp[i\u22121])<\/code><\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Base cases: <\/strong>\n        <ul>\n            <li>If <code>n == 0<\/code> \u2192 return 0<\/li>\n            <li>If <code>n == 1<\/code> \u2192 return <code>val[0]<\/code><\/li>\n            <li><strong>Initialize: <\/strong>\n            <ul>\n                <li><code>dp[0] = val[0]<\/code><\/li>\n                <li><code>dp[1] = max(val[0], val[1])<\/code><\/li>\n            <\/ul>\n            <\/li>\n        <\/ul>\n    <\/li>\n\n    <li>\n        <strong>Optimization:\n            <ul>\n                <li>Notice that to compute <code>dp[i]<\/code>, we only need the last <strong>two states (dp[i-1] and dp[i-2])<\/strong>.<\/li>\n                <li>So instead of a full array, we use <strong>two variables<\/strong>:\n                    <ul>\n                        <li><code>p1<\/code> \u2192 previous <code>(dp[i-1])<\/code><\/li>\n                        <li>p2 \u2192 second previous <code>(dp[i-2])<\/code><\/li>\n                    <\/ul>\n\n                <\/li>\n            <\/ul>\n        <\/strong>\n    <\/li>\n<\/ul>\n\n    <h2>Time & Space Complexity:<\/h2>\n    <p><strong>Time Complexity:<\/strong> <code>O(n)<\/code><\/p>\n    <p><strong>Space Complexity:<\/strong> <code>O(1)<\/code><\/p>\n\n<h2>Dry Run<\/h2> \n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\"> \n  <p><strong>Input:<\/strong> <code>val = [2, 7, 9, 3, 1]<\/code><\/p> \n  \n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\n\nStep 0: Start Function: rob([2, 7, 9, 3, 1])\nn = 5\np1 = 0\np2 = 0\n\nIteration (i = 0):\n- curr = Math.max(val[0] + p2, p1)\n       = Math.max(2 + 0, 0)\n       = 2\n- temp = p1 = 0\n- p1 = curr = 2\n- p2 = temp = 0\n- curr++ \u2192 curr = 3 (but not used further)\nState \u2192 p1 = 2, p2 = 0\n\nIteration (i = 1):\n- curr = Math.max(val[1] + p2, p1)\n       = Math.max(7 + 0, 2)\n       = 7\n- temp = p1 = 2\n- p1 = curr = 7\n- p2 = temp = 2\n- curr++ \u2192 curr = 8\nState \u2192 p1 = 7, p2 = 2\n\nIteration (i = 2):\n- curr = Math.max(val[2] + p2, p1)\n       = Math.max(9 + 2, 7)\n       = 11\n- temp = p1 = 7\n- p1 = curr = 11\n- p2 = temp = 7\n- curr++ \u2192 curr = 12\nState \u2192 p1 = 11, p2 = 7\n\nIteration (i = 3):\n- curr = Math.max(val[3] + p2, p1)\n       = Math.max(3 + 7, 11)\n       = 11\n- temp = p1 = 11\n- p1 = curr = 11\n- p2 = temp = 11\n- curr++ \u2192 curr = 12\nState \u2192 p1 = 11, p2 = 11\n\nIteration (i = 4):\n- curr = Math.max(val[4] + p2, p1)\n       = Math.max(1 + 11, 11)\n       = 12\n- temp = p1 = 11\n- p1 = curr = 12\n- p2 = temp = 11\n- curr++ \u2192 curr = 13\nState \u2192 p1 = 12, p2 = 11\n\nLoop ends (i = n)\n\nStep 3: End\nReturn p1 = 12\n  <\/pre> \n  \n  <p><strong>Output:<\/strong> <code>12<\/code><\/p> \n<\/div>\n\n        <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/09\/Screenshot-2025-09-26-at-11.49.43\u202fAM.png\" alt=\"Stocks\" \/>\n   \n<\/div>\n\n\n  <div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n      <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\nvar rob = function(val) { \n    let n = val.length; \n    if(n == 1) \n    return val[0]; \n    \n    let p2 = p1 = 0; \n    for(let i=0; i < n; i++){ \n        curr = Math.max(val[i] + p2, p1); \n        let temp = p1; \n        p1 = curr; \n        p2 = temp; \n        curr++; \n     } \n    return p1; \n};\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\ndef rob(val):\n    n = len(val)\n    if n == 1:\n        return val[0]\n    p1 = p2 = 0\n\n    for i in range(n):\n        curr = max(val[i] + p2, p1)\n        temp = p1\n        p1 = curr\n        p2 = temp\n        curr += 1\n    return p1\n      <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\npublic class Solution {\n    public static long rob(int[] val) {\n        int n = val.length;\n        if (n == 1) return val[0];\n        long p1 = 0, p2 = 0;\n\n        for (int i = 0; i < n; i++) {\n            long curr = Math.max((long)val[i] + p2, p1);\n            long temp = p1;\n            p1 = curr;\n            p2 = temp;\n            curr++;\n        }\n        return p1;\n    }\n\n    public static void main(String[] args) {\n        int[] arr = {2,7,9,3,1};\n        System.out.println(rob(arr));\n    }\n}\n    <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n<!-- #include &lt;vector&gt; -->\n#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nlong long rob(const vector<int>& val) {\n    int n = val.size();\n    if (n == 1) return val[0];\n    long long p1 = 0, p2 = 0;\n    for (int i = 0; i < n; ++i) {\n        long long curr = max((long long)val[i] + p2, p1);\n        long long temp = p1;\n        p1 = curr;\n        p2 = temp;\n        curr++;\n    }\n    return p1;\n}\n\/\/ Example usage\nint main() {\n    vector<int> v = {2,7,9,3,1};\n    cout << rob(v) << endl;\n    return 0;\n}\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\nlong long rob(int *val, int n) {\n    if (n == 1) return val[0];\n    long long p1 = 0, p2 = 0;\n\n    for (int i = 0; i < n; ++i) {\n        long long candidate1 = (long long)val[i] + p2;\n        long long curr = candidate1 > p1 ? candidate1 : p1;\n        long long temp = p1;\n        p1 = curr;\n        p2 = temp;\n        curr++;\n    }\n    return p1;\n}\nint main() {\n    int arr[] = {2,7,9,3,1};\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    printf(\"%lld\\n\", rob(arr, n));\n    return 0;\n}\n <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n      <pre><code class=\"language-csharp\">\nusing System;\n\nclass Solution {\n    public static long Rob(int[] val) {\n        int n = val.Length;\n        if (n == 1) return val[0];\n        long p1 = 0, p2 = 0;\n\n        for (int i = 0; i < n; i++) {\n            long curr = Math.Max((long)val[i] + p2, p1);\n            long temp = p1;\n            p1 = curr;\n            p2 = temp;\n            curr++;\n        }\n        return p1;\n    }\n\n    static void Main() {\n        int[] arr = {2,7,9,3,1};\n        Console.WriteLine(Rob(arr));\n    }\n}\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,322,260,176,175,211,811,810,174,172,173],"tags":[],"class_list":{"0":"post-10119","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms","7":"category-algorithms-and-data-structures","8":"category-c-c-plus-plus","9":"category-csharp","10":"category-cplusplus","11":"category-data-structures","12":"category-data-structures-and-algorithms","13":"category-dsa","14":"category-java","15":"category-javascript","16":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10119"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10119\/revisions"}],"predecessor-version":[{"id":10120,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10119\/revisions\/10120"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}